链表经典OJ问题详解
文章目录
前言
链表是一种基础且重要的数据结构，在程序设计中有着广泛的应用。由于其物理存储的非连续性，链表在插入、删除操作上具有独特的优势，但也给某些操作（如随机访问）带来了挑战。在技术面试和算法竞赛中，链表相关的题目出现频率极高，熟练掌握链表的常见操作和经典问题的解法，是每个程序员必备的技能。本文精选了10道经典的链表OJ题目，从思路分析到C语言代码实现，逐步详解，并穿插了快慢指针、哑结点等常用技巧的讲解，每道题目都附带了对应的在线练习链接，方便读者动手实践。希望能帮助读者深入理解链表，轻松应对各类链表问题。
1. 删除链表中等于给定值 val 的所有结点
题目描述
删除链表中所有值为 val 的结点，返回删除后的链表头结点。🔗 力扣 203. 移除链表元素
思路分析
创建一个带哨兵位的新链表，将符合条件的节点接到新链表后面，然后返回哨兵位的next节点，注意尾节点的next需要置为NULL，如果原链表是空链表，那么直接返回空链表。
代码实现
typedef struct ListNode ListNode; struct ListNode* removeElements(struct ListNode* head, int val) { if(head==NULL) { return NULL; } ListNode* newhead,* newtail; newhead=newtail=(ListNode*)malloc(sizeof(ListNode)); ListNode* pcur=head; while(pcur) { if(pcur->val!=val) { newtail->next=pcur; newtail=newtail->next; } pcur=pcur->next; } newtail->next=NULL; return newhead->next; }2. 反转一个单链表
题目描述
反转一个单链表，返回反转后的链表头结点。🔗 力扣 206. 反转链表
思路分析
迭代法：使用三个指针 prev、curr、next。初始时 prev 为 NULL，curr 指向头结点。每次将 curr->next 指向 prev，然后三个指针整体后移，直到 curr 为 NULL，此时 prev 即为新头结点。
代码实现
typedef struct ListNode ListNode; struct ListNode* reverseList(struct ListNode* head) { ListNode* n1,*n2,*n3; if(head==NULL) return head; n1=NULL,n2=head,n3=head->next; while(n2) { n2->next=n1; n1=n2; n2=n3; if(n3) n3=n3->next; } return n1; }3. 链表的中间结点
题目描述
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。🔗 力扣 876. 链表的中间结点
思路分析
快慢指针法：定义两个指针 slow 和 fast，初始都指向头结点。slow 每次走一步，fast 每次走两步。当 fast 到达链表末尾时，slow 恰好指向中间结点。若链表长度为偶数，fast 为空时 slow 指向第二个中间结点。
代码实现
typedef struct ListNode ListNode; struct ListNode* middleNode(struct ListNode* head) { /*int count=0; if(head==NULL) return head; ListNode* pcur=head; while(pcur) { pcur=pcur->next; count++; } pcur=head; for(int i=0;i<count/2;i++) { pcur=pcur->next; } return pcur; */ ListNode* slow,*fast; slow=fast=head; while(fast&&fast->next)//这里注意顺序不能更改 { fast=fast->next->next; slow=slow->next; } return slow; }4. 链表中倒数第k个结点
题目描述
输入一个链表，输出该链表中倒数第k个结点。🔗 力扣 面试题 22. 链表中倒数第k个节点
思路分析
双指针法：定义两个指针 fast 和 slow，初始都指向头结点。先让 fast 指针向前移动 k 步，然后 fast 和 slow 同时移动。当 fast 到达链表末尾时，slow 恰好指向倒数第k个结点。需要注意 k 大于链表长度的情况。
代码实现
typedef struct ListNode Listnode; struct ListNode* trainingPlan(struct ListNode* head, int cnt) { Listnode* fast=head,* slow=head; if(head==NULL) return NULL; while(cnt--) { fast=fast->next; } while(fast) { fast=fast->next; slow=slow->next; } return slow; }5. 合并两个有序链表
题目描述
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。🔗 力扣 21. 合并两个有序链表
思路分析
迭代法：创建一个虚拟头结点 dummy，用 tail 指针指向新链表的尾部。首先判断两个链表中有无空链表，返回其中非空链表，然后比较两个链表当前结点的值，将较小的结点接到 tail 后面，并移动对应链表的指针。当其中一个链表遍历完后，将另一个链表的剩余部分直接接上。
代码实现
typedef struct ListNode ListNode; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { ListNode* l1 = list1; ListNode* l2 = list2; ListNode* newhead = NULL; ListNode* newtail = NULL; // 处理空链表情况 if (l1 == NULL) return l2; if (l2 == NULL) return l1; // 确定第一个节点（初始化 newhead 和 newtail） if (l1->val < l2->val) { newhead = newtail = l1; l1 = l1->next; } else { newhead = newtail = l2; l2 = l2->next; } while (l1 && l2) { if (l1->val < l2->val) { newtail->next = l1; // 将 l1 节点挂到尾部 l1 = l1->next; // l1 后移 } else { newtail->next = l2; // 将 l2 节点挂到尾部 l2 = l2->next; // l2 后移 } newtail = newtail->next; // newtail 移动到新节点 } if (l1) newtail->next = l1; if (l2) newtail->next = l2; return newhead; }6. 链表分割
题目描述
编写代码，以给定值 x 为基准将链表分割成两部分，所有小于 x 的结点排在大于或等于 x 的结点之前，且保持原来的相对顺序。 分割链表
思路分析
创建两个哑结点，分别作为小于 x 的部分和大于等于 x 的部分的头结点。遍历原链表，根据结点值的大小分别接到对应的链表后面。最后将两部分连接起来，注意要将大于等于部分链表的尾结点的 next 置空，避免形成环。
代码实现
typedef struct ListNode ListNode; struct ListNode* partition(struct ListNode* head, int x) { if(head==NULL) { return NULL; } ListNode* lesshead,* lesstail; ListNode* greathead,* greattail; lesshead=lesstail=(ListNode*)malloc(sizeof(ListNode)); greathead=greattail=(ListNode*)malloc(sizeof(ListNode)); ListNode* pcur=head; while(pcur) { if((pcur->val)<x) { lesstail->next=pcur; lesstail=lesstail->next; } else { greattail->next=pcur; greattail=greattail->next; } pcur=pcur->next; } greattail->next=NULL; lesstail->next=greathead->next; ListNode* ret=lesshead->next; free(lesshead); free(greathead); return ret; }7. 链表的回文结构
题目描述
判断一个链表是否为回文结构。🔗 力扣 234. 回文链表
思路分析
三步走：1）使用快慢指针找到链表的中间结点；2）反转后半部分链表；3）比较前半部分和反转后的后半部分是否相同。最后最好将链表恢复原状（可选）。
代码实现
typedef struct ListNode Listnode; //找到中间节点 Listnode* get_middlenode(Listnode* head) { Listnode* fast=head,* slow=head; while(fast&&fast->next) { fast=fast->next->next; slow=slow->next; } return slow; } //翻转 Listnode* reverse(Listnode* middlenode) { Listnode* prev = NULL; Listnode* curr = middlenode; while (curr) { Listnode* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } bool isPalindrome(struct ListNode* head) { if(head==NULL) return NULL; Listnode* reversehead=reverse(get_middlenode(head)); Listnode* p1=head,* p2=reversehead; while(p1&&p2) { if(p1->val!=p2->val) { return false; } p1=p1->next; p2=p2->next; } return true; }8. 相交链表
题目描述
输入两个链表，找出它们的第一个公共结点。🔗 力扣 160. 相交链表
思路分析
双指针法：创建两个指针 pA 和 pB，分别指向两个链表的头结点。两个指针同时移动，当 pA 到达链表末尾时，重定向到链表B的头结点；当 pB 到达链表末尾时，重定向到链表A的头结点。最终两个指针会在相交结点相遇（若无相交，则同时指向 NULL）。
代码实现
typedef struct ListNode Listnode; struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { Listnode* pcur1=headA,* pcur2=headB; int count1=0,count2=0; while(pcur1->next) { pcur1=pcur1->next; count1++; } while(pcur2->next) { pcur2=pcur2->next; count2++; } if(pcur1!=pcur2) { return NULL; } int gap=abs(count1-count2); Listnode* longlist=headA,* shortlist=headB; if(count2>count1) { longlist=headB; shortlist=headA; } while(gap--) { longlist=longlist->next; } while(longlist!=shortlist) { longlist=longlist->next; shortlist=shortlist->next; } return longlist; }9. 判断链表中是否有环
题目描述
给定一个链表，判断链表中是否有环。🔗 力扣 141. 环形链表
思路分析
快慢指针法：定义 slow 和 fast 指针，slow 每次走一步，fast 每次走两步。如果链表有环，则两个指针最终会在环中相遇；如果 fast 到达链表末尾（NULL），则说明链表无环。
代码实现
typedef struct ListNode listnode; bool hasCycle(struct ListNode *head) { listnode* fast=head,* slow=head; while(fast&&fast->next) { fast=fast->next->next; slow=slow->next; if(fast==slow) { return true; } } return false; }10. 返回链表开始入环的第一个结点
题目描述
给定一个链表，返回链表开始入环的第一个结点。如果链表无环，则返回 NULL。🔗 力扣 142. 环形链表 II
思路分析
在上一题判断有环的基础上，记录快慢指针相遇点。然后让一个指针从链表头开始，另一个指针从相遇点开始，两个指针每次都走一步，它们相遇的位置就是环的入口结点。数学推导可参考文档中的证明：设头结点到环入口距离为 L，环入口到相遇点距离为 X，环长度为 R，则有 L = nR - X（n为快指针在环中绕的圈数）。
代码实现
typedef struct ListNode Listnode; struct ListNode *detectCycle(struct ListNode *head) { Listnode* fast=head,* slow=head; Listnode* meet=NULL; while(fast&&fast->next) { fast=fast->next->next; slow=slow->next; if(fast==slow) { meet=fast; fast=NULL; } } if(meet==NULL) return NULL; Listnode* pcur=head; while(pcur!=meet) { meet=meet->next; pcur=pcur->next; } return meet; }结语
链表作为数据结构的基础，其核心在于指针的灵活操作和边界条件的处理。通过以上10道经典题目的练习，相信大家已经掌握了链表操作的基本技巧：
- 哑结点的应用简化了头结点特殊情况的处理
- 快慢指针是解决环问题、中间结点问题的利器
- 双指针法在合并、相交等问题中表现出色
- 反转链表的迭代和递归两种思路需要熟练掌握
链表的题目看似变化多端，但万变不离其宗。只要理解链表的结构特点，勤加练习，就能在面试和竞赛中游刃有余。建议读者在LeetCode上将这些题目逐个AC（Accept），并在解题过程中思考多种解法的优劣，逐步提升自己的算法思维。
最后，数据结构的学习是一个循序渐进的过程，链表之后还有栈、队列、树等更复杂的数据结构等待我们去探索。打好基础，方能行稳致远。
