1.环形链表1.1 环形链表1https://leetcode.cn/problems/linked-list-cycle//** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedefstructListNodeListNode;boolhasCycle(structListNode*head){if(headNULL||head-nextNULL){returnfalse;}ListNode*slowhead;ListNode*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast){returntrue;}}returnfalse;}解题思路快慢指针想象两个人在环形跑道上跑步一个人跑得快每次两步一个人跑得慢每次一步如果跑道是环形的那么快的人最终会追上慢的人也就是相遇。如果跑道是直的无环快的人会先跑到终点NULL。在链表中我们设置两个指针slow每次走一步fast每次走两步从 head 出发如果链表有环则 fast 一定会追上 slow它们相遇如果无环fast 会先遇到 NULL。思路还是很简单的就是简单的快慢指针但是我们在这里来点更深层次的思考这里有如下两个问题思考1为什么快指针每次走两步慢指针走一步可以相遇有没有可能遇不上请推理证明答案是肯定的以下为证明由于fast与slow的相对速度差为1假设我们设在slow进环时slow与fast的距离为N那么下一次由于速度差为1所以下一次的距离为N-1,以此类推。下一次就是N-2…直到3210。所以由此可见当相对速度差为1时是一定可以相遇的即当N等于0时就相遇了。思考2快指针一次走3步走4步…n步行吗?我们来总结一下总结一下1、N是偶数第一轮就追上了2、N是奇数第一轮追击会错过距离变成C-1a、如果C-1是偶数下一轮就追上了b、如果C-1是奇数那么就永远追不上那么我们再来思考一个问题存不存在一种情况不可能追得上呢要想满足这个条件是不是就是得保证N是奇数同时C-1是奇数也就是说C是偶数的情况呢我们来试着证明看看综上所述不存在一定不可能追得上的情况。只有奇数-奇数才能等于偶数偶数一定是偶数(x1)∗偶数一定是偶数所以反正N是奇数且C的偶数不能同时存在永远追不上的条件不成立结论一定能追上N偶数第一轮就追上了N是奇数第一轮追不上C-1是偶数第二轮就追上1.2 环形链表2https://leetcode.cn/problems/linked-list-cycle-ii/description//** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedefstructListNodeListNode;structListNode*detectCycle(structListNode*head){if(headNULL||head-nextNULL){returnNULL;}ListNode*slowhead;ListNode*fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast){ListNode*meetslow;while(head!meet){meetmeet-next;headhead-next;}returnmeet;}}returnNULL;}当快慢指针相遇时将 meet 指向相遇点此时 slow 和 fast 都在相遇点。然后让 head 指针从链表头开始meet 指针从相遇点开始两者同时每次移动一步。根据数学推导当它们再次相遇时相遇点即为环的入口。循环条件 head ! meet 保证了只要两个指针不相等就继续移动。一旦相等循环结束返回此时的节点即入口。为什么这样能找到入口设头节点到环入口的距离为 a环入口到相遇点的距离为 b顺时针方向相遇点到环入口的距离为 c即环剩余部分环长 L b c当快慢指针相遇时慢指针走了 a b 步快指针走了 a b nL 步n 为快指针在环内多走的圈数。由于快指针速度是慢指针的两倍有2(ab)abnLabnLanL-b(n-1)Lc这意味着从相遇点出发走 c 步即可到达入口而从 head 出发走 a 步也到达入口且 a 正好等于 (n-1)L c。因此让两个指针分别从 head 和相遇点以相同速度移动它们必然在入口处相遇。也就是说其实就是在head向入口走时meet一直在环内绕圈。2.随机链表的复制https://leetcode.cn/problems/copy-list-with-random-pointer/description//** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */typedefstructNodeNode;structNode*copyRandomList(structNode*head){Node*currhead;//拷贝while(curr){Node*copy(Node*)malloc(sizeof(Node));copy-valcurr-val;copy-nextcurr-next;curr-nextcopy;currcopy-next;}currhead;while(curr){Node*copycurr-next;if(curr-randomNULL){copy-randomNULL;}else{copy-randomcurr-random-next;}currcopy-next;}currhead;Node*newHeadNULL;Node*TailNULL;while(curr){Node*copycurr-next;Node*nextcopy-next;if(TailNULL){newHeadTailcopy;}else{Tail-nextcopy;Tailcopy;}currnext;}returnnewHead;}代码整体结构拷贝节点并插入原链表在原节点后插入复制节点设置复制节点的 random 指针分离原链表和复制链表拆分成两个独立的链表这种做法的核心思想是利用原节点的 next 指针建立原节点与复制节点的一一对应关系从而方便地找到 random 指针应该指向的复制节点。第一部分拷贝节点并插入思路遍历原链表对每个原节点 curr创建一个新节点 copy值与原节点相同。将 copy 插入到 curr 和 curr-next 之间copy-next 指向 curr 原来的下一个节点。curr-next 指向 copy。然后 curr 移动到 copy-next即原链表的下一个节点继续处理。第二部分设置复制节点的 random思路再次遍历每次处理一对节点原节点 curr 和它的复制节点 copy即 curr-next。原节点的 random 可能指向某个节点 rand那么复制节点的 random 就应该指向 rand 的复制节点即 rand-next因为每个原节点的复制节点都在它后面。如果 curr-random 为 NULL则复制节点的 random 也设为 NULL。第三部分分离两个链表思路再次遍历交错链表这次要把它拆分成两个独立链表原链表每个原节点的 next 应该指向它原来的下一个原节点即 copy-next。复制链表每个复制节点的 next 应该指向下一个复制节点。