目录
引言
这个专题专门讲解链表的带环问题,并且对面试有关链表带环的问题进行分析,这次重点讲解三道题,分别是:
大家可以先去看看,好了,话不多说,正片开始.
环形链表
题目描述:
给你一个链表的头节点 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 <= 105pos为-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指针相遇,而我们呢?
环形链表Ⅱ
题目描述:
给定一个链表的头节点 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 <= 105pos的值为-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;
}
随机链表的复制
题目描述:
给你一个长度为 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 <= 104Node.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;
}小结
到这里关于链表专题真正的完结了,后面我会更新栈和队列这两个数据结构的实现和有关的经典算法题,包括贪吃蛇项目也会尽快的发布,如果这篇博客对大家有帮助的话,一定要点赞关注哦!这是你们对我最大的支持,好了,我们下期再见!