链表经典面试题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 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 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 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; }

        小结

        到这里关于链表专题真正的完结了,后面我会更新栈和队列这两个数据结构的实现和有关的经典算法题,包括贪吃蛇项目也会尽快的发布,如果这篇博客对大家有帮助的话,一定要点赞关注哦!这是你们对我最大的支持,好了,我们下期再见!