【数据结构】面试OJ题——带环链表（数学推论）

 

目录

1.环形链表Ⅰ

​编辑

思路 ：

思路拓展 

问题一：

问题二：

总结： 

问题三：

证明总结第三点 

 总结：

2. 环形链表Ⅱ

思路一

思路二 

3.相交链表 

 思路：

---

 

1.环形链表Ⅰ

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

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

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

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

思路 ：

        我们考虑环状时，如果是简单的循环next来判定，只会进入死循环；

需要引入新思维，判断是否带环，可以想象操场追赶问题，两个人在操场跑；让一个人先进场跑，再让另外一名选手进场，如果环足够大，如何让后入场的选手追赶上前面的；答案是，后来者加快速度。

        而在这道题中，我们用快慢指针概念，一个指针走两步，一个走一步，进入环后，快指针一定会和慢指针相遇

为什么一定会相遇呢？

距离为N，每次快指针走两步，慢指针走一步相当于距离每次减少1；

如此距离缩短，肯定会相遇，而当快慢指针相遇的时候，就是证明该链表带环；

而如果不带环，快指针将链表走完后，表明退出了循环即可； 

 

 

bool hasCycle(struct ListNode *head) {
    //快慢指针
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    
    while(fast && fast->next)
    {
         fast = fast->next->next;
        slow = slow->next;
       if(fast == slow)
       {
           return true;
       }
    }
    return false;
}

思路拓展 

上面说到，距离缩小1一定会追上，那如果距离一次缩小2呢，是不是更快的会相遇呢

如果一次距离缩小n，是不是更快呢；如此延申，我们可以发现有三个拓展

 1. slow一次走一步，fast一次走两步，一定会相遇吗

2.slow一次走一步，fast一次走三步，一定会相遇吗

3.slow一次走n步，fast一次走m步，一定会相遇吗        （m>n>1）

问题一：

 距离缩小为1的话，一定会遇上，我们上面证明了

问题二：

 当slow进环时，fast和它的距离为N，一次减少2。分为两种情况

1.当N是偶数时：

2.当N是奇数时：

所以，我们可以发现，当N是偶数时，依然可以追上

当N是奇数是，得到下一轮：

这时候要看 C-1是奇偶数

如果c-1是偶数：在下一轮就会追上，

如果c-是奇数：则会开始无限循环下去，一直追击不上；

总结： 

1.如果N是偶数，第一轮内就会追上；

2.如果N是奇数，C是奇数，第一轮会错过，下一轮会追击（C是奇数，C-1就会是偶数）；

3.如果N是奇数，C是偶数，就永远追不上；

问题三：

 这个类似问题二，每次距离缩小是m-n(>=1);

如果N%(m-n) == 0  说明一圈就可以追上；

如果是-1，则是C-1，-2就是C-2；

如果这个数是m-n的倍数，如果不是倍数，则可能存在死循环        

证明总结第三点 

写到这里时，问题二的 总结第三点，是否真的成立呢？

3.如果N是奇数，C是偶数，就永远追不上；

 此刻，slow走了L的路程，fast走了 L + nC - N； 

在这时，可以推论出公式 

 

 推论出来的这个公式：

2L：一定是偶数，

n*C:总结第三点假设这里是偶数；

N：如果要满足此公式，N就不可能会奇数，

所以， 3.如果N是奇数，C是偶数，就永远追不上；

这句话的条件不成立

 总结：

1.如果N是偶数，第一轮内就会追上；

2.如果N是奇数，C是奇数，第一轮会错过，下一轮会追击（C是奇数，C-1就会是偶数）；

只存在这两种

bool hasCycle(struct ListNode *head) {
    //快慢指针
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    
    while(fast && fast->next)
    {
         fast = fast->next->next;
        slow = slow->next;
       if(fast == slow)
       {
           return true;
       }
    }
    return false;
}

 

在这种情况下，该情况其实还可以推论出另一个公式结论 。这就是第二题

2. 环形链表Ⅱ

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

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

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

不允许修改 链表。

思路一

 我们依旧用上一道题的画图思路来解决，

第一步先判断是否存在环，

第二部找到入口点；

 

用快慢指针方法，slow走一步，fast走两步

 

struct ListNode *detectCycle(struct ListNode *head) {
    //快慢指针
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    
    while(fast && fast->next)
    {
         fast = fast->next->next;
        slow = slow->next;
       if(fast == slow) //相遇了
       {
        struct ListNode* meet = slow;
          while(head != meet)   //起点和相遇点
          {
              head = head->next;
              meet = meet->next;
          }
          //找到入口点了
          return meet;
       }
    }
    return false;
}

思路二 

 这道题还有另外一种解法，就是在相遇点meet这里，将下一个节设为newnode，再将meet->next置NULL，这样就将带环链表问题转换成 相交链表问题

而这种解法自然有相交链表的题；

但是这种解法比较复杂，建议用思路一的

3.相交链表 

160. 相交链表 - 力扣（LeetCode）

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

 

 思路：

题目两种情况，存在相交和不相交，

相交还有前后长短问题；

1.先判断是否有相交点；如果相交，尾节点一定相同；

2.计算两条链表的长度，让长链表先走差距步，这样可以让两条链表处于相同head；

3.再让两条链接一起走，直到遇到相同点；

返回相遇点或者是结束链表遍历返回NULL；

 

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA = headA,*curB = headB;
    //计算两条链表长度
    int lenA = 0;
    int lenB = 0;
    while(curA)
    {
        lenA++;
        curA = curA->next;
    }
    while(curB)
    {
        lenB++;
        curB = curB->next;
    }
 
    //算出长度差
    int n = abs(lenA-lenB);
    //假设lenA 长于lenB
    struct ListNode* longlist = headA,*shortlist = headB;
    if(lenB>lenA) //假设不成立，交换
    {
        longlist = headB;
        shortlist = headA;
    }
    //长的先走差值
    while(n--)
    {
        longlist = longlist->next;
    }
    //判断是否相等
    while(longlist != shortlist)
    {
        longlist = longlist->next;
        shortlist = shortlist->next; 
    }
    //到这里要么相等，要么链表不相交，已经走完了是NULL
    return longlist;
}