单链表经典算法题（C语言）

单链表经典算法题详解C语言前言链表是数据结构中的重要基础也是面试中的高频考点。本文将用C语言详细讲解六道经典的单链表算法题每道题都提供完整的思路分析和代码实现。1. 移除链表元素LeetCode 203题目LeetCode 203. 移除链表元素解题思路删除链表节点需要注意如果头节点就是要删除的值需要移动头指针删除节点时需要让前驱节点指向后继节点推荐使用哨兵位哑节点简化边界条件处理代码实现/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */structListNode*removeElements(structListNode*head,intval){// 使用哨兵位避免单独处理头节点structListNode*sentinel(structListNode*)malloc(sizeof(structListNode));sentinel-nexthead;structListNode*prevsentinel;structListNode*currhead;while(curr!NULL){if(curr-valval){// 删除当前节点prev-nextcurr-next;free(curr);currprev-next;}else{prevcurr;currcurr-next;}}headsentinel-next;free(sentinel);returnhead;}2. 反转链表LeetCode 206题目LeetCode 206. 反转链表解题思路方法一迭代法推荐使用三个指针prev、curr、next遍历链表逐个反转节点的指向。structListNode*reverseList(structListNode*head){structListNode*prevNULL;structListNode*currhead;while(curr!NULL){structListNode*nextcurr-next;// 保存下一个节点curr-nextprev;// 反转指针prevcurr;// 移动prevcurrnext;// 移动curr}returnprev;// prev指向新的头节点}方法二递归法structListNode*reverseList(structListNode*head){// 递归终止条件if(headNULL||head-nextNULL){returnhead;}structListNode*newHeadreverseList(head-next);head-next-nexthead;head-nextNULL;returnnewHead;}3. 合并两个有序链表LeetCode 21题目LeetCode 21. 合并两个有序链表解题思路使用哨兵位比较两个链表当前节点的值将较小的节点接入结果链表。代码实现structListNode*mergeTwoLists(structListNode*list1,structListNode*list2){// 创建哨兵位structListNode*sentinel(structListNode*)malloc(sizeof(structListNode));structListNode*tailsentinel;while(list1!NULLlist2!NULL){if(list1-vallist2-val){tail-nextlist1;list1list1-next;}else{tail-nextlist2;list2list2-next;}tailtail-next;}// 连接剩余部分tail-next(list1!NULL)?list1:list2;structListNode*resultsentinel-next;free(sentinel);returnresult;}4. 链表的中间结点LeetCode 876题目LeetCode 876. 链表的中间结点解题思路快慢指针法慢指针每次走一步快指针每次走两步快指针走到末尾时慢指针正好在中间代码实现structListNode*middleNode(structListNode*head){structListNode*slowhead;structListNode*fasthead;while(fast!NULLfast-next!NULL){slowslow-next;// 走一步fastfast-next-next;// 走两步}returnslow;}5. 约瑟夫问题环形链表题目牛客网 BM44 有效括号序列 / 约瑟夫问题或 LeetCode 剑指 Offer 62. 圆圈中最后剩下的数字解题思路方法一环形链表模拟typedefstructListNode{intval;structListNode*next;}ListNode;// 创建循环链表ListNode*createCircularList(intn){ListNode*head(ListNode*)malloc(sizeof(ListNode));head-val1;head-nextNULL;ListNode*prevhead;for(inti2;in;i){ListNode*node(ListNode*)malloc(sizeof(ListNode));node-vali;node-nextNULL;prev-nextnode;prevnode;}prev-nexthead;// 形成环returnhead;}intjosephus(intn,intm){if(n1)return1;ListNode*headcreateCircularList(n);ListNode*prevNULL;ListNode*currhead;while(n1){// 报数1到m走m-1步到达要删除的节点for(intcount1;countm;count){prevcurr;currcurr-next;}// 删除curr节点prev-nextcurr-next;free(curr);currprev-next;n--;}intresultcurr-val;free(curr);returnresult;}方法二数学递推最优解约瑟夫问题有数学递推公式f(1) 00-based编号f(n) (f(n-1) m) % nintjosephus(intn,intm){intsurvivor0;// f(1) 0for(inti2;in;i){survivor(survivorm)%i;}returnsurvivor1;// 转回1-based编号}6. 分割链表面试题 02.04题目LeetCode 面试题 02.04. 分割链表解题思路创建两个链表一个存放小于x的节点另一个存放大于等于x的节点最后连接起来。代码实现structListNode*partition(structListNode*head,intx){// 创建两个链表的哨兵位structListNode*lessHead(structListNode*)malloc(sizeof(structListNode));structListNode*greaterHead(structListNode*)malloc(sizeof(structListNode));structListNode*lessTaillessHead;structListNode*greaterTailgreaterHead;structListNode*currhead;while(curr!NULL){if(curr-valx){lessTail-nextcurr;lessTaillessTail-next;}else{greaterTail-nextcurr;greaterTailgreaterTail-next;}currcurr-next;}// 连接两个链表lessTail-nextgreaterHead-next;greaterTail-nextNULL;// 重要防止成环headlessHead-next;free(lessHead);free(greaterHead);returnhead;}7.常见技巧总结技巧适用场景核心思想哨兵位删除节点、合并链表避免单独处理头节点快慢指针找中间节点、环检测步长差异制造相遇点三指针反转链表逐个改变节点指向数学递推约瑟夫问题找规律推导递推公式双链表模拟分割链表分开处理再合并结语链表题的核心在于理清节点之间的指向关系多画图、多练习熟能生巧。上述六道题涵盖了链表算法中最经典的模式掌握它们将为你后续学习更复杂的数据结构打下坚实基础。希望这篇文章对你有所帮助欢迎在评论区交流讨论