链表经典面试题02--链表的带环问题

引言

环形链表

题目描述:

思路分析:

代码展示:

面试中遇到的问题:

环形链表Ⅱ

题目描述:

思路分析:

代码展示:

面试中遇到的问题:

方法二:

随机链表的复制

题目描述:

思路分析:

代码展示:

小结

引言

这个专题专门讲解链表的带环问题,并且对面试有关链表带环的问题进行分析,这次重点讲解三道题,分别是:

141. 环形链表 - 力扣（LeetCode）

142. 环形链表 II - 力扣（LeetCode）

138. 随机链表的复制 - 力扣（LeetCode）

大家可以先去看看,好了,话不多说,正片开始.

环形链表

--141. 环形链表 - 力扣（LeetCode）

题目描述:

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。
进阶：你能用 O(1)（即，常量）内存解决此问题吗？

思路分析:

这道题用快慢指针的方法会非常简单,关于快慢指针的方法我在链表经典面试题01-CSDN博客和单链表经典算法-CSDN博客中均有详细讲解,大家可以先看看,这里就不过多介绍,简而言之就是定义两个指针,一个为慢指针,一次走一步,一个为快指针,一次走两步,当它们两个相遇时,即为环形链表,快慢指针法在链表中很常见,大家一定要牢牢掌握.

代码展示:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {struct ListNode* fast = head, * slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast) return true;}return false;
}

面试中遇到的问题:

代码很简单,但在面试时,面试官往往会问一下两个问题:

1.为什么一定会相遇,有没有可能错过,永远追不上?请证明

2.slow一次走一步,fast走三步四步,五步,n步行吗?请证明

我们先看第一个问题:它们两个一定会相遇吗?会不会永远追不上

我们知道,在不带环链表中,它们两个永远都不会相遇,所以我们只需要在带环链表中去证明

我们先随便列举一种情况,如下图:

当slow进入环中,fast和slow相距为N,现在fast要追slow,fast每次二步,slow每次一步,每追击一次,它们两个的距离就减一,直到它们两个相遇,所以它们两个一定会相遇.

再看问题二: slow一次走一步,fast走三步四步,五步,n步行吗?请证明

先对这个问题进行分析,图还是上面一样的图:

这里,我们先列举fast为3的情况:

也就时每次追击,它们两个的距离就减二,这就会分成两种情况:

1.当N为偶数时:它们两个相遇了

2.当N为奇数时:fast会刚好错过slow,进入新一轮的追击,如下图所示:

这时,追击的距离不在是N,而是C-1,也就是环的周长减一,这时候又有两种情况:

1.C-1为偶数,那么它们第二轮直接追上

2.C-1为奇数,那么它们又会错过,进入新的追击

总结一下:

也就是说,只有当N为奇数并且C-1为奇数时,它们两个永远不会相遇一直错过,世界上最遥远的距离莫过于此

难道真相真的就如此悲伤吗?

大家先别急,有反转

刚才我们分析了需要N为奇数且C-1为奇数才会一直错过,可是,有没有可能这中情况永远不会存在呢?往这个方向,我们进入新一轮的分析:

这里就需要用数学去寻找等式,如下图:

slow走的距离是: L

fast走的距离是:L + x*C +C-N

注意:slow进环时,fast已经在环里转了x圈,但具体圈数我们不知道

根据fast走的距离是slow的三倍,可得出下列等式:

3*L = L + x*C + C-N

化简后得:

2*L = (x+1)*C - N

在根据我们之前得出得结论:需要N和C-1同时为奇数,那就用假设法,看是否成立

C-1为奇数,C也就是偶数

我们左边的等式显然是偶数,右边(x+1)*C显然也是偶数,而N为奇数,偶数减去奇数还是奇数,假设不成立,所以它们两个是无法同时为奇数

在进一步推理我们可以得到:

N是奇数时,C也是奇数

N为偶数时,C也是偶数

所以最终得结论时:

一定能追上

N为偶数第一轮就追上了

N为奇数第一轮追不上,C-1时偶数第二轮就追上了

那么fast走四步甚至n步也是同样得分析方式,只不过情况更加复杂,但一定能追上

有得时候真羡慕fast指针,任何情况,无论它走多少步,它都能与它心爱得slow指针相遇,而我们呢?

环形链表Ⅱ

142. 环形链表 II - 力扣（LeetCode）

题目描述:

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

思路分析:

这到题也有一种很简单得思路,先用我们上面刚刚讲解过得快慢指针找出它们两个相遇得起始点,再让相遇得点和起始得点同时走,它们两个一定会相遇,如下图所示:

代码展示:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* slow = head, * fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;//相遇if(fast == slow){struct ListNode* meet = slow;while(meet != head){meet = meet->next;head = head->next;}return meet;}}return NULL;
}

面试中遇到的问题:

这个不用多说,面试官肯定会问你为什么这样它们两个一定会在起始点相遇

我们还是需要跟上面一道题一样--找等式

相遇时:

slow走得距离为: L + N

fast走得距离为: L + x*C + N

fast走得路程是slow得两倍

2*(L+N) = L + x*C + N

化简得到:L = x*C -N

也就是说,它们两个同时走时,head走过L,meet会走过x圈,刚好在起始点相遇,就是这么巧合

方法二:

我们在判断是否有无环时,返回相遇点,将相遇点赋予新的指针,而后将相遇的下一个位置置为NULL,这样他就不是一个带环链表,变成了求两个链表的相交点,如下图所示:

因为求两个链表的相交问题我之前在链表经典面试题01-CSDN博客中的相交链表详细讲解过,这里就不在多说直接给出代码:
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* curA = headA, *curB = headB;int lenA = 0, lenB = 0;while(curA->next){curA = curA->next;++lenA;}while(curB->next){curB = curB->next;++lenB;}//尾节点不相交返回空if(curA != curB) return NULL;int gap = abs(lenA - lenB);struct ListNode* longList = headA, * shortList = headB;if(lenB > lenA){longList = headB;shortList = headA;}while(gap--){longList = longList->next;}while(longList != shortList){longList = longList->next;shortList = shortList->next;}return shortList;
}

代码展示:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* curA = headA, *curB = headB;int lenA = 0, lenB = 0;while(curA->next){curA = curA->next;++lenA;}while(curB->next){curB = curB->next;++lenB;}//尾节点不相交返回空if(curA != curB) return NULL;int gap = abs(lenA - lenB);struct ListNode* longList = headA, * shortList = headB;if(lenB > lenA){longList = headB;shortList = headA;}while(gap--){longList = longList->next;}while(longList != shortList){longList = longList->next;shortList = shortList->next;}return shortList;
}struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* fast = head, * slow = head;struct ListNode* cur = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){struct ListNode* meet = slow->next;slow->next = NULL;return getIntersectionNode(head, meet);}}return NULL;
}

随机链表的复制

138. 随机链表的复制 - 力扣（LeetCode）

题目描述:

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码只接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

提示：

0 <= n <= 1000
-104 <= Node.val <= 104
Node.random 为 null 或指向链表中的节点。

思路分析:

这道题得数据范围为:10^4,说明我们的时间复杂度可以是O(N^2),不过写起来还是挺麻烦的,这里,我推荐一种很妙的解法,将我们需要拷贝的新链表与原链表连接起来,方便random指针进行指向,如下图所示:

我们先遍历原链表一次将我们所需要拷贝的节点进行插入,在遍历一次链表,将random进行指向的拷贝,最后将我们拷贝的节点尾插到新链表中,返回新链表的头节点.

代码展示:

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {struct Node* cur = head;while(cur){struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;copy->next = cur->next;cur->next = copy;cur = copy->next;}cur = head;while(cur){struct Node* copy = cur->next;if(cur->random == NULL){copy->random = NULL;}else{copy->random = cur->random->next;}cur = copy->next;}//把拷贝节点取下来尾插成新链表,然后回复原链表struct Node* copyhead = NULL, *copytail = NULL;cur = head;while(cur){struct Node* copy = cur->next;struct Node* next = copy->next;  if(copytail == NULL){copyhead = copytail = copy;}else{copytail->next = copy;copytail = copytail->next;}cur->next = next;cur = next;}return copyhead;
}