链表带环问题

文章目录

• 1.1环形链表
• • 1.2为什么快指针每次走两步，慢指针走一步可以？
  • • 1.3为什么快指针每次走三步，慢指针走一步不一定相遇？
    • • 1.4求链表环的入口点

1.1环形链表

1. 给定一个链表，判断链表中是否有环。
   

   
   

   (OJ链接)
   

2. 思路：“快慢指针”------快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾
3. 时间复杂度：0(n) 空间复杂度O(1)

class Solution {
public:
    bool hasCycle(ListNode *head) 
    {
        ListNode* slow = head;
        ListNode* fast = head;
        //快慢指针
        while(fast != NULL && fast->next != NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)
            {
                return true;
            }
        }
        return false;    
    }
};

---

1.2为什么快指针每次走两步，慢指针走一步可以？

1. slow走一步，fast走二步，它们一起能相遇吗？请证明：
   答案是：一定可以相遇！
   解释：假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。
   

   
   

   当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。
   

   
   

   此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
   

   
   

1.3为什么快指针每次走三步，慢指针走一步不一定相遇？

2. slow走一步，fast走三步它们能相遇吗？请证明：
   答案是：不一定。
   

   
   

   
   解释：假设链表带环，两个指针最后都会进入环，快指针肯定先进环，慢指针后进环。
   

   
   

   每次追击slow和fast的距离缩短2(fast走的步数减去slow的步数)。
   

   
   

   如果slow和fast的距离为偶数，那么一定能相遇，如果是奇数那么环长度减一是偶数也能相遇，如果环长度减一是奇数，那么就永远不会相遇
   

1.4求链表环的入口点

3. 给定一个链表，返回链表开始入环的第一个节点。
   

   
   

   如果链表无环，则返回 NULL。
   

   
   

   (OJ链接)
   

3. 思想：让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。
   

   
   

   
   

class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != NULL && fast->next != NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
            while(slow == fast)
            {
                ListNode* meet = slow;
                while(meet != head)
                {
                    meet = meet->next;
                    head = head->next;
                }
                return meet;
            }
        }
        return NULL;
    }
};