文章目录问题一删除链表中特定值节点(LC203)一问题描述二解题思路三代码实现思路2四代码解析问题二反转链表(LC206)一问题描述二解题思路三代码实现思路2四代码解析问题三合并两个有序链表(LC21)一问题描述二解题思路三代码实现问题四找链表中间节点(LC876)一问题描述二解题思路三代码实现问题五链表分割按值分区(面试题02.04)一问题描述二解题思路三代码实现(思路3)问题六约瑟夫环问题一问题描述二解题思路三代码实现四代码解析问题一删除链表中特定值节点(LC203)一问题描述给定链表头节点head和整数val删除所有值等于val的节点返回新头节点。示例1输入head [1,2,6,3,4,5,6], val 6输出[1,2,3,4,5]示例 2输入head [], val 1输出[]示例 3输入head [7,7,7,7], val 7输出[]二解题思路思路1遍历数组值等于val则释放当前节点思路2创建新链表值不等于val则尾插到新链表三代码实现思路2/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedefstructListNodeLN;structListNode*removeElements(structListNode*head,intval){LN*newHeadNULL;LN*newTailNULL;LN*pcurhead;while(pcur){if(pcur-val!val){//为空if(newHeadNULL){newHeadpcur;newTailpcur;}else{newTail-nextpcur;newTailnewTail-next;}}pcurpcur-next;}if(newTail!NULL)newTail-nextNULL;returnnewHead;}四代码解析化新链表头尾指针用newHead记录新链表头节点newTail维护新链表尾节点初始均为NULL。遍历原链表通过pcur指针遍历输入的原链表head。筛选保留节点遇到值不等于val的节点时若新链表为空newHead是NULL该节点同时作为新链表的头和尾若新链表非空将该节点链接到新链表尾部更新newTail。处理新链表尾节点遍历结束后将新链表尾节点的next置为NULL。如果没有这行代码节点5依旧指向原来指向的节点也就是节点6返回的链表就是[1,2,3,4,5,6]问题二反转链表(LC206)一问题描述给定链表头节点反转链表并返回新头节点。示例1输入head [1,2,3,4,5]输出[5,4,3,2,1]示例2输入head [1,2]输出[2,1]示例 3输入head []输出[]二解题思路思路1创建一个新的链表依次头插在新链表前思路2创建3个指针完成链表翻转三代码实现思路2/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedefstructListNodeLN;structListNode*reverseList(structListNode*head){if(headNULL)returnhead;LN*n1,*n2,*n3;n1NULL;n2head;n3n2-next;while(n2!NULL){n2-nextn1;n1n2;n2n3;if(n3)n3n3-next;}returnn1;}四代码解析指针初始化n1 初始化为 NULL表示反转后当前节点的前一个节点初始时没有节点所以为 NULL n2 初始化为 head从原链表头节点开始处理 n3 初始化为 head-next提前保存当前节点的下一个节点防止后续指针修改后找不到 。反转循环在while (n2 ! NULL)循环中n2-next n1; 实现当前节点 n2 指向其前一个节点 n1 完成指针反转。然后n1 n2; n2 n3;让三个指针依次向后移动准备处理下一个节点。if (n3 ! NULL)判断下一个节点是否存在存在则更新n3 n3-next保证循环能持续推进。返回结果当循环结束时n2 为 NULL 此时 n1 指向的就是反转后链表的头节点返回 n1 。问题三合并两个有序链表(LC21)一问题描述将两个升序链表合并为一个新升序链表返回。示例1输入l1 [1,2,4], l2 [1,3,4]输出[1,1,2,3,4,4]示例 2输入l1 [], l2 []输出[]示例 3输入l1 [], l2 [0]输出[0]二解题思路创建新链表遍历原来两个链表将较小值尾插到新链表遍历结果只有两种l1为空或者l2为空把不为空的l1或l2尾插到新链表三代码实现typedefstructListNodeLN;structListNode*mergeTwoLists(structListNode*list1,structListNode*list2){LN*l1list1;LN*l2list2;if(l1NULL)returnl2;if(l2NULL)returnl1;LN*newHeadNULL;LN*newTailNULL;while(l1l2){if(l1-vall2-val){if(newHeadNULL){newHeadnewTaill1;}else{newTail-nextl1;newTailnewTail-next;}l1l1-next;}else{if(newHeadNULL){newHeadnewTaill2;}else{newTail-nextl2;newTailnewTail-next;}l2l2-next;}}if(l1){newTail-nextl1;}if(l2){newTail-nextl2;}returnnewHead;}优化后typedefstructListNodeLN;structListNode*mergeTwoLists(structListNode*list1,structListNode*list2){LN*l1list1;LN*l2list2;if(l1NULL)returnl2;if(l2NULL)returnl1;LN*newHeadNULL;LN*newTailNULL;newHeadnewTail(LN*)malloc(sizeof(LN));while(l1l2){if(l1-vall2-val){newTail-nextl1;newTailnewTail-next;l1l1-next;}else{newTail-nextl2;newTailnewTail-next;l2l2-next;}}if(l1){newTail-nextl1;}if(l2){newTail-nextl2;}LN*retnewHead-next;free(newHead);newHeadNULL;returnret;}注意动态开辟的内存要手动释放问题四找链表中间节点(LC876)一问题描述找到单链表中间节点若有两个中间节点返回第二个。示例1输入head [1,2,3,4,5]输出[3,4,5]解释链表只有一个中间结点值为 3 。示例2:输入head [1,2,3,4,5,6]输出[4,5,6]解释该链表有两个中间结点值分别为 3 和 4 返回第二个结点。二解题思路思路1计数器遍历链表得到总数再遍历一半找到中间节点思路2快指针fast每次走两步慢指针slow每次走一步。当fast走到末尾slow指向中间节点。三代码实现ListNode*middleNode(ListNode*head){ListNode*slowhead;ListNode*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;}returnslow;}注意奇数个节点fast走到最后恰好slow走到中间节点偶数个节点fast就需要走到空slow走到第二个中间节点因此循环条件fast fast-next顺序不可以更改因为存在逻辑短路当fast为空就不会对fast解引用访问问题五链表分割按值分区(面试题02.04)一问题描述给定链表头节点和特定值x使所有小于x的节点在大于等于x节点之前无需保留原相对位置。示例1:输入head [1,4,3,2,5,2], x 3输出[1,2,2,4,3,5]示例 2输入head [2,1], x 2输出[1,2]二解题思路思路1:在原链表上进行修改,若pcur值小于x,往后走若大于或等于x,尾插在链表后,删除旧节点思路2:创建新链表,遍历原链表若pcur值小于x,则头插在新链表中若大于或等于x,尾插在链表后思路3:创建小链表和大链表若pcur小于x值尾插小链表大于或等于x值尾插在大链表小链表尾节点和大链表头节点相连三代码实现(思路3)typedefstructListNodeLN;structListNode*partition(structListNode*head,intx){if(headNULL)returnNULL;LN*lessHead,*lessTail,*greaterHead,*greaterTail;lessHeadlessTail(LN*)malloc(sizeof(LN));greaterHeadgreaterTail(LN*)malloc(sizeof(LN));LN*pcurhead;while(pcur){if(pcur-valx){lessTail-nextpcur;lessTaillessTail-next;}else{greaterTail-nextpcur;greaterTailgreaterTail-next;}pcurpcur-next;}//把尾节点下一个节点置为空,如果不写这行代码会出现死循环(5-2)greaterTail-nextNULL;//两个链表相连lessTail-nextgreaterHead-next;LN*tmplessHead-next;free(lessHead);lessHeadNULL;free(greaterHead);greaterHeadNULL;returntmp;}问题六约瑟夫环问题一问题描述n个人围成圈从第1人开始报数报到m的人离开最后留下的人编号是多少。著名的Josephus问题据说著名犹太历史学家 Josephus有过以下的故事在罗马人占领乔塔帕特后39 个犹太人与Josephus及他的朋友躲到⼀个洞中39个犹太人决定宁愿死也不要被人抓到于是决定了一个自杀方式41个人排成⼀个圆圈由第1个人开始报数每报数到第3人该人就必须自杀然后再由下一个重新报数直到所有人都自杀身亡。然而Josephus 和他的朋友并不想遵从Josephus要他的朋友先假装遵从他将朋友与⾃⼰安排在第16个与第31个位置于是逃过了这场死亡游戏。示例1输入5,2返回值3说明开始5个人 12345 从1开始报数1-12-2编号为2的人离开1345从3开始报数3-14-2编号为4的人离开135从5开始报数5-11-2编号为1的人离开35从3开始报数3-15-2编号为5的人离开最后留下人的编号是3示例2输入1,1返回值1二解题思路根据n创建带环链表遍历带环链表,计数器来模拟报数三代码实现typedefstructListNodeLN;LN*buyListNode(intval){LN*newNode(LN*)malloc(sizeof(LN));newNode-valval;returnnewNode;}LN*createCircle(intn){LN*phead(LN*)malloc(sizeof(LN));LN*ptailphead;// 初始化头节点值为1phead-val1;// 创建2到n号节点for(inti2;in;i){ptail-nextbuyListNode(i);ptailptail-next;}// 尾节点指向头节点形成环ptail-nextphead;returnptail;}intysf(intn,intm){LN*prevcreateCircle(n);// prev指向尾节点LN*pcurprev-next;// pcur指向头节点第一个人intcount1;// 报数计数器// 当只剩一个节点时结束循环while(pcur-next!pcur){// 当报数到 m时移除当前节点if(countm){prev-nextpcur-next;// 跳过当前节点free(pcur);// 释放内存pcurprev-next;// 移动到下一个节点count1;// 重置计数器}else{// 未报数到 m继续移动指针prevpcur;pcurpcur-next;count;}}// 返回最后剩下的节点的值returnpcur-val;}四代码解析使用prev和pcur两个指针追踪当前节点和前一个节点count变量记录当前报数当count等于 m 时将前一个节点的 next 指向当前节点的 next实现当前节点的移除释放被移除节点的内存重置计数器继续下一轮报数循环终止条件当链表中只剩一个节点pcur-next pcur