当前位置：首页 > news >正文

环形链表问题与随机链表的复制oj复盘

news 2026/5/12 16:58:01

1.环形链表

1.1 环形链表1

https://leetcode.cn/problems/linked-list-cycle/

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */typedefstructListNodeListNode;boolhasCycle(structListNode*head){if(head==NULL||head->next==NULL){returnfalse;}ListNode*slow=head;ListNode*fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){returntrue;}}returnfalse;}

解题思路：快慢指针

想象两个人在环形跑道上跑步：

一个人跑得快（每次两步）
一个人跑得慢（每次一步）
如果跑道是环形的，那么快的人最终会追上慢的人（也就是相遇）。如果跑道是直的（无环），快的人会先跑到终点（NULL）。

在链表中，我们设置两个指针：

slow：每次走一步
fast：每次走两步
从 head 出发，如果链表有环，则 fast 一定会追上 slow（它们相遇）；如果无环，fast 会先遇到 NULL。

思路还是很简单的，就是简单的快慢指针，但是我们在这里来点更深层次的思考，这里有如下两个问题：

思考1：为什么快指针每次走两步，慢指针走一步可以相遇，有没有可能遇不上，请推理证明！
答案是肯定的，以下为证明：
由于fast与slow的相对速度差为1，假设我们设在slow进环时，slow与fast的距离为N，那么下一次由于速度差为1，所以下一次的距离为N-1,以此类推。下一次就是N-2，…，直到，3，2，1，0。
所以由此可见当相对速度差为1时，是一定可以相遇的，即当N等于0时就相遇了。

思考2：快指针一次走3步，走4步，…n步行吗?

我们来总结一下：
总结一下：

1、N是偶数，第一轮就追上了
2、N是奇数，第一轮追击会错过，距离变成C-1
a、如果C-1是偶数，下一轮就追上了
b、如果C-1是奇数，那么就永远追不上

那么我们再来思考一个问题，存不存在一种情况不可能追得上呢？
要想满足这个条件，是不是就是得保证N是奇数同时C-1是奇数，也就是说C是偶数的情况呢？
我们来试着证明看看：

综上所述：
不存在一定不可能追得上的情况。
只有奇数-奇数才能等于偶数
偶数一定是偶数
(x+1)∗偶数一定是偶数

所以反正N是奇数且C的偶数不能同时存在，永远追不上的条件不成立

结论：一定能追上

N偶数第一轮就追上了
N是奇数第一轮追不上，C-1是偶数第二轮就追上

1.2 环形链表2

https://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(head==NULL||head->next==NULL){returnNULL;}ListNode*slow=head;ListNode*fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast){ListNode*meet=slow;while(head!=meet){meet=meet->next;head=head->next;}returnmeet;}}returnNULL;}

当快慢指针相遇时，将 meet 指向相遇点（此时 slow 和 fast 都在相遇点）。
然后让 head 指针从链表头开始，meet 指针从相遇点开始，两者同时每次移动一步。
根据数学推导，当它们再次相遇时，相遇点即为环的入口。
循环条件 head != meet 保证了只要两个指针不相等就继续移动。
一旦相等，循环结束，返回此时的节点（即入口）。

为什么这样能找到入口？
设：

头节点到环入口的距离为 a
环入口到相遇点的距离为 b（顺时针方向）
相遇点到环入口的距离为 c（即环剩余部分，环长 L = b + c）
当快慢指针相遇时，慢指针走了 a + b 步，快指针走了 a + b + nL 步（n 为快指针在环内多走的圈数）。由于快指针速度是慢指针的两倍，有：

2(a+b)=a+b+nL=>a+b=nL=>a=nL-b=(n-1)L+c

这意味着从相遇点出发，走 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*curr=head;//拷贝while(curr){Node*copy=(Node*)malloc(sizeof(Node));copy->val=curr->val;copy->next=curr->next;curr->next=copy;curr=copy->next;}curr=head;while(curr){Node*copy=curr->next;if(curr->random==NULL){copy->random=NULL;}else{copy->random=curr->random->next;}curr=copy->next;}curr=head;Node*newHead=NULL;Node*Tail=NULL;while(curr){Node*copy=curr->next;Node*next=copy->next;if(Tail==NULL){newHead=Tail=copy;}else{Tail->next=copy;Tail=copy;}curr=next;}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。

第三部分：分离两个链表
思路