欢迎各位大佬光临本文章！！！

还请各位大佬提出宝贵的意见，如发现文章错误请联系冰冰，冰冰一定会虚心接受，及时改正。

本系列文章为冰冰学习编程的学习笔记，如果对您也有帮助，还请各位大佬、帅哥、美女点点支持，您的每一分关心都是我坚持的动力。

我的博客地址：bingbing~bang的博客_CSDN博客https://blog.csdn.net/bingbing_bang?type=bloghttps://blog.csdn.net/bingbing_bang?type=blog

我的gitee：

冰冰棒 (bingbingsupercool) - Gitee.comhttps://gitee.com/bingbingsurercoolhttps://gitee.com/bingbingsurercool

系列文章推荐

冰冰学习笔记：这些链表练习题，你会吗？（上）

冰冰学习笔记：这些链表练习题，你会吗？（中）

目录

系列文章推荐

前言

1.快慢指针步数问题

2.环形链表的第一个交点

（1）找到交点，两指针分别走，相遇即为交点

（2）从相遇点断开，转换为找相交链表交点问题

3.复制带随机指针的链表

前言

        链表练习题的最后两道题来了，两道题的难度稍有上升，同样的带环链表，这次的链表练习题主要是理解起来难，代码书写并不难。上一节中提到的快慢指针来找是否有环，快指针一次走两步，慢指针一次走一步能够成功追上。但是，快指针如果一次走三步呢？四步呢？是否还能追上呢？下面我们一一解决这些问题。

1.快慢指针步数问题

        我们知道快指针一次走两步，慢指针一次走一步，两个指针在环中一定能追到，可是为什么呢？

        原因很简单，如果有环存在，当慢指针进入环时，快指针早已在环中，假设环的大小为C，两指针相距的距离为X，此时两个指针一个走一步，一个走两步，那么快指针相对于慢指针的速度为1，之间的距离每次就会减少1，距离变为X-1,X-2,......2,1,0.最终距离一定会变为0，因此二者一定会追上。

        那快指针一次走三步呢？能否还能追上呢？此时就不一定能追上了。还是和上面一样，我们设环的大小为C，当慢指针进入环后，两指针之间追及的距离为X。此时，快指针相对于慢指针的速度为2，两者之间的距离X每次减少2，若X为偶数：X，X-2，X-4 …… 4，2，0.此种情况下是可以追上的，但是如果X为奇数：X，X-2，X-4 ……3，1，-1.此种情况下二者错过，之间的距离X改变，变为C-1，此时又取决于C-1是偶数还是奇数，如果是偶数，可以追上，如果是奇数会发现追不上。

2.环形链表的第一个交点

题目链接：142. 环形链表 II - 力扣（LeetCode）

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

        看到这个题目，我们最先想到的就是记录每个结点，当再次回到交点时必然与记录的节点中有相同的地址，然后返回此地址。这种方法可行，但是不够简单。我们看看下面的解法。 

（1）找到交点，两指针分别走，相遇即为交点

        什么意思呢？就是我们先用快慢指针找到在环中的交点meet，然后一个指针从头开始，一个指针从meet开始，每次走一步，当这两个指针相遇的时候就是入环的第一个交点。

        啥，为啥呀？

        下面我们分析一下，假设入环前的距离为L，当慢指针入环后，快指针在环中已经走了很久，环的大小为C，如果C很小，那么在慢指针进入环的时候，快指针就有可能在环中走了好几圈，如果C很大，慢指针入环的时候，快指针有可能一圈没有走完。因此我们设快指针走的圈数为N。当两指针在meet处相遇后，设慢指针走的距离为X，那么慢指针从头开始到相遇点一共走了L+X。快指针走了多少呢？当快指针从环内走到meet相遇慢指针，快指针至少走了一圈，N最小为1，然后又走了X到相遇点，所以快指针走了L+X+N*C。

        我们要注意，慢指针最大也就是走一圈，也就是说X的距离最大是C，因为快指针速度为慢指针的二倍，最坏的情况就是快指针在慢指针前面一步，然后进行追及，当慢指针走半圈时，快指针走一圈，当慢指针走一圈时，快指针走两圈，最终追上。

        所以就可以推出公式：2(L+X)=L+N*C+X ，进行化简可得到：L+X=N*C  --->  L=(N-1)*C+C-X

        (N-1)*C为绕环的距离，从meet处开始，无论(N-1)*C多大，都会在meet处停下来。所以两指针分别从头和meet处走，一定会相遇在交点处。

 代码如下：

struct ListNode* detectCycle(struct ListNode* head){    struct ListNode* slow;    struct ListNode* fast;    struct ListNode* phead;    slow = fast = phead = head;    while ( fast && fast->next )    { //要让指针先走 fast = fast->next->next; slow = slow->next; if ( fast == slow ) {     struct ListNode* meet = fast;     while ( meet != phead )     {  meet = meet->next;  phead = phead->next;     }     return meet; }    }    return NULL;}

（2）从相遇点断开，转换为找相交链表交点问题

        当然我们还有其他的解法，即利用上一节讲到的知识，我们先使用快慢指针找到相遇点meet，然后将相遇点meet的next保存到新的指针newhead里，然后将meet->next置为NULL。这样我们就得到了两个链表，并且这两个链表还是相交的，然后将问题转化为求两个链表第一个交点的位置。

所以代码为：

struct ListNode* detectCycle(struct ListNode* head){    struct ListNode* slow, * fast;    struct ListNode* meet;    struct ListNode* newhead;    slow = fast = head;    int flag = 1;    while ( fast && fast->next )    { fast = fast->next->next; slow = slow->next; //从交点断开 if ( fast == slow ) {     meet = fast;     newhead = meet->next;     meet->next = NULL;     flag = 0;     break; }    }    if ( flag == 1 )    { return NULL;    }    //转化为找链表相交的第一个交点    int len1 = 1;    int len2 = 1;    struct ListNode* cur = head;    while ( cur->next )    { cur = cur->next; len1++;    }    cur = newhead;    while ( cur->next )    { cur = cur->next; len2++;    }    struct ListNode* shortlen = head;    struct ListNode* longlen = newhead;    if ( len1 > len2 )    { shortlen = newhead; longlen = head;    }    int gap = abs(len1 - len2);    while ( gap-- )    { longlen = longlen->next;    }    while ( shortlen != longlen )    { shortlen = shortlen->next; longlen = longlen->next;    }    return shortlen;}

3.复制带随机指针的链表

题目链接：138. 复制带随机指针的链表 - 力扣（LeetCode）

题目描述：

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

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

        这个题目就是让你将题目给出的链表复制一份，复制出来的新链表与原链表完全一样，里面的random指针指向的也是新链表中的元素，且指向方式也是和原链表一样。如下图所示：

       新链表的结构与原来的链表的结构完全一样，指向关系也一样。新链表需要开辟出来。

       那应该怎么做呢？我们没有办法进行简单的复制，数值可以复制，但是原链表中random指针指向的位置无法简单的复制。复制下来指向的也是原链表的结点。例如我们复制数值为13的结点，但是如果将random直接复制过来，random指向的还是原链表中7的结点，而不是新链表中7的结点。

        我们可以在原链表的基础上进行新链表的链接，将每一创建好的新链表的结点直接插入到旧链表结点的后面。这样新链表的random就是旧链表random指向的结点的下一个结点。然后进行链接即可。

        链接完毕后，将两个链表分离，旧链表还原。

具体代码如下：

struct Node* copyRandomList(struct Node* head){    struct Node* cur = head;    if ( cur == NULL )    { return NULL;    }    //插入新结点    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;    }    //改变新结点的random的指向    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;    }    //分离新链表,还原旧链表    cur = head;    struct Node* newhead = (struct Node*)malloc(sizeof(struct Node));    newhead->next = NULL;    struct Node* tail = newhead;    while ( cur )    { struct Node* copy = cur->next; struct Node* next = copy->next; tail->next = copy; tail = tail->next; cur->next = next; cur = next; }    tail->next = NULL;    struct Node* tmp = newhead->next;    free(newhead);    return tmp;}