前言单链表是数据结构与算法面试和笔试中的高频考点。本文旨在整理一系列经典的单链表OJOnline Judge题目提供清晰的解题思路、关键步骤分析和可直接运行的代码实现以C语言为主供大家参考也方便自己复习时快速回顾思考。1. 移除链表元素题目描述给你一个链表的头节点head和一个整数val请你删除链表中所有满足Node.val val的节点并返回新的头节点。OJ链接解题思路使用哨兵节点dummy node简化边界条件处理。遍历链表当遇到值等于val的节点时跳过该节点否则将节点连接到新链表。typedef struct ListNode ListNode; struct ListNode* removeElements(struct ListNode* head, int val) { ListNode* dummy (ListNode* )malloc(sizeof(ListNode)); dummy-next NULL; ListNode* ptail dummy; ListNode* pcur head; while(pcur) { if(pcur-val ! val) { ptail-next pcur; ptail ptail-next; } pcur pcur-next; } ptail-next NULL; return dummy-next; }2. 反转链表题目描述给定单链表的头节点head请反转链表并返回反转后的头节点。OJ链接解题思路迭代法使用三个指针prev、pcur和next遍历链表逐个改变节点指向。typedef struct ListNode ListNode; struct ListNode* reverseList(struct ListNode* head) { ListNode* newhead NULL; ListNode* pcur head; ListNode* next NULL; while(pcur) { next pcur-next; pcur-next newhead; newhead pcur; pcur next; } return newhead; }3. 链表的中间结点题目描述给定一个头节点为head的非空单链表返回链表的中间节点。如果有两个中间节点则返回第二个中间节点。OJ链接解题思路快慢指针法慢指针每次走一步快指针每次走两步。当快指针到达链表末尾时慢指针正好指向中间节点。typedef struct ListNode ListNode; struct ListNode* middleNode(struct ListNode* head) { ListNode* slow,* fast; slow fast head; while(fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } return slow; }4. 链表中倒数第K个节点题目描述输入一个链表输出该链表中倒数第k个节点。为了符合大多数人的习惯本题从1开始计数即链表的尾节点是倒数第1个节点。解题思路双指针法让快指针先走k步然后快慢指针同时前进。当快指针到达链表末尾时慢指针正好指向倒数第k个节点。OJ链接typedef struct ListNode ListNode; int kthToLast(struct ListNode* head, int k) { ListNode* slow NULL; ListNode* fast NULL; fast slow head; int i k-1; while(i--) { fast fast-next; } while(fast-next ! NULL) { fast fast-next; slow slow-next; } return slow-val; }5. 合并两个有序链表题目描述将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。OJ链接解题思路创建一个哨兵节点dummy node作为新链表的起始点然后比较两个链表当前节点的值将较小的节点连接到新链表后直到某个链表遍历完再将另一个链表的剩余部分接上。typedef struct ListNode ListNode; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { ListNode* n1,* n2,* ptail,* phead; n1 list1,n2 list2,ptail phead (ListNode*)malloc(sizeof(ListNode)); if(n1 NULL) return n2; if(n2 NULL) return n1; else { while(n1 n2) { if(n1-val n2-val) { ptail-next n1; ptail ptail-next; n1 n1-next; } else { ptail-next n2; ptail ptail-next; n2 n2-next; } } if(n1 NULL) { ptail-next n2; } else { ptail-next n1; } ListNode* ret phead-next; free(phead); return ret; } }6. 链表分割题目描述给你一个链表的头节点head和一个特定值x请你对链表进行分隔使得所有小于x的节点都出现在大于或等于x的节点之前。你应当保留两个分区中每个节点的初始相对位置。OJ链接解题思路创建两个哨兵节点分别用于存放小于x的节点和大于等于x的节点。遍历原链表根据节点值的大小分别连接到对应的链表中最后将两个链表连接起来。typedef struct ListNode ListNode; struct ListNode* partition(struct ListNode* head, int x) { ListNode* Large,* Small,* pcur,* SmallHead,* LargeHead; Large Small SmallHead NULL; pcur head; if(head NULL) return NULL; else { while(pcur) { if(pcur-val x) { if(Small NULL) { SmallHead Small pcur; } else { Small-next pcur; Small Small-next; } } else { if(Large NULL) { LargeHead Large pcur; } else { Large-next pcur; Large Large-next; } } pcur pcur-next; } if(Small NULL) { Large-next NULL; return LargeHead; } else if(Large NULL) { return SmallHead; } else { Large-next NULL; Small-next LargeHead; return SmallHead; } } }7. 回文链表题目描述给你一个单链表的头节点head请你判断该链表是否为回文链表。如果是返回true否则返回false。OJ链接解题思路找到链表中点反转后半部分链表然后比较前后两部分是否相同。typedef struct ListNode ListNode; ListNode* ListReverse(ListNode* head) { ListNode* n1,* n2,* n3; if(head NULL) { return NULL; } n1 NULL,n2 head,n3 head-next; while(n2) { n2-next n1; n1 n2; n2 n3; if(n3) { n3 n3-next; } } return n1; } bool isPalindrome(struct ListNode* head) { ListNode* slow,* fast,* prev; slow fast head; prev NULL; while(fast fast-next) { prev slow; slow slow-next; fast fast-next-next; } prev NULL; ListNode* p2 ListReverse(slow); ListNode* p1 head; while(p1 p2) { if(p1-val ! p2-val) { return false; } p1 p1-next; p2 p2-next; } return true; }8. 相交链表题目描述给你两个单链表的头节点headA和headB请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点返回NULL。OJ链接解题思路双指针法指针pA从headA开始pB从headB开始。当pA走到链表末尾时重定向到headB当pB走到链表末尾时重定向到headA。如果两链表相交它们最终会相遇在交点如果不相交最终会同时到达NULL。typedef struct ListNode ListNode; struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { ListNode* pcurA headA,* pcurB headB; int countA 0,countB 0; while(pcurA) { pcurA pcurA-next; countA; } while(pcurB) { pcurB pcurB-next; countB; } pcurA headA,pcurB headB; int diff countA - countB; if(diff0) { while(diff--) { pcurA pcurA-next; } } else if(diff0) { while(diff) { pcurB pcurB-next; } } while(pcurA ! pcurB) { pcurA pcurA-next; pcurB pcurB-next; } return pcurA; }9. 带环链表9.1 判断链表是否有环题目描述给定一个链表判断链表中是否有环。如果链表中存在环则返回true否则返回false。OJ链接解题思路快慢指针法Floyd判圈算法慢指针每次走一步快指针每次走两步。如果存在环快慢指针最终会相遇如果快指针到达链表末尾NULL则说明链表无环。typedef struct ListNode ListNode; bool hasCycle(struct ListNode *head) { ListNode *slow head, *fast head; while (fast amp;amp; fast-gt;next) { fast fast-gt;next-gt;next; slow slow-gt;next; if (fast slow) return true; } return false; }9.2 找到环的入口节点题目描述给定一个链表如果链表有环返回环的入口节点如果没有环返回NULL。OJ链接解题思路方法一快慢指针法Floyd判圈算法的扩展1. 使用快慢指针判断链表是否有环并找到相遇点2. 将其中一个指针重新指向链表头部3. 两个指针以相同速度每次一步前进再次相遇的节点即为环的入口数学原理设链表头到环入口的距离为 a环入口到相遇点的距离为 b相遇点到环入口的距离为 c。快指针走的距离是慢指针的两倍2(ab) a b n(bc)。化简得 a (n-1)(bc) c。这意味着从链表头到环入口的距离等于从相遇点走到环入口的距离加上 (n-1) 圈环长。typedef struct ListNode ListNode; ListNode* IsCircle(struct ListNode *head) { ListNode* fast,*slow; fast slow head; while(fast fast-next) { fast fast-next-next; slow slow-next; if(fast slow) { return fast; } } return NULL; } struct ListNode *detectCycle(struct ListNode *head) { ListNode* meet IsCircle(head); if(!meet) { return NULL; } else { ListNode* start head; while(meet ! start) { meet meet-gt;next; start start-gt;next; } return meet; } }方法二先判断相遇节点再断环转换为相交节点问题1. 使用快慢指针找到环内的相遇节点同方法一2. 从相遇节点处将环断开得到两个独立的链表3. 问题转化为求两个链表的相交节点问题参考第8题4. 找到相交节点后恢复原链表结构可选思路解析当快慢指针在环内相遇时相遇节点将环分成了两部分。如果从相遇节点处断开环原链表就变成了两个独立的链表一个是从头节点到相遇节点的链表A另一个是从相遇节点的下一个节点开始沿着环走回到相遇节点的链表B。这两个链表的相交节点就是环的入口节点。这样问题就转化为了经典的“相交链表”问题可以使用第8题的双指针法来解决。留给读者思考如何具体实现断环操作断开后如何恢复原链表结构这种方法的时间复杂度和空间复杂度是多少与Floyd算法相比有什么优缺点10. 总结本文系统梳理了单链表相关的九类经典OJ题目涵盖了从基础操作到复杂算法的完整知识体系基础操作移除元素、反转链表、寻找中间节点和倒数第K个节点这些是链表操作的基本功。合并与分割合并有序链表和链表分割展示了如何处理多个链表以及如何按条件重新组织链表结构。链表特性应用回文链表检测巧妙结合了快慢指针和链表反转体现了对链表结构的深入理解。链表关系判断相交链表和带环链表是链表问题的进阶考点需要掌握双指针技巧和数学推理。核心技巧总结哨兵节点Dummy Node简化边界条件处理避免空指针异常。双指针技巧快慢指针用于寻找中点、检测环前后指针用于反转、删除等操作。问题转化如将带环链表入口问题转化为相交链表问题体现了算法设计的灵活性。空间复杂度优化多数解法都能在O(1)额外空间内完成体现了链表的优势。学习建议先理解每种解法的核心思想再动手实现代码注意边界条件的处理特别是空链表、单节点链表等情况多画图分析指针移动过程帮助理解复杂操作尝试用不同方法解决同一问题比较各种解法的优劣掌握这些经典题目后面对链表相关面试题时就能从容应对。建议读者在理解本文思路的基础上独立完成代码实现并思考每种方法的变体和优化空间。