---

版权声明：本文为博主原创文章，转载请注明出处。
个人博客地址：https://yangyuanlin.club
欢迎来踩~~~~

---

Linked List Cycle I

Given a linked list, determine if it has a cycle in it.

Follow up: Can you solve it without using extra space?

Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Follow up: Can you solve it without using extra space?

• 题目大意：（I）给定一个链表，判断这个单链表中是否有环。（II）给定一个单链表，返回单链表的环的起点。如果单链表中没有环，返回null。进一步考虑：你能解决这两个问题但是不用额外的空间吗？ps：意思就是让你不要用额外的空间。

• （I）思路：对于第一个问题，我一开始觉得，设置两个指针，一个指向头结点，一个向后查找，如果重新查找到了头结点，就说明有环，但是，情况并非都是这么理想的，比如：

  
  
  

  看到这种情况，就想自己果然还是太年轻了，于是就想到用HashSet，每访问一个节点，就将其记录下来，第一次重复访问了某一个节点时，就说明链表有环，而且该点就是环的起点。

public boolean hasCycle2(ListNode head) {
    if (head == null) {
        return false;
    }
    HashSet<ListNode> set = new HashSet<ListNode>();
    while (head != null) {
        if (set.contains(head)) {
            return true;
        }
        set.add(head);
        head = head.next;
    }
    return false;
}

• 然而建立哈希表需要额外O(n)的空间开销，于是开始搜集资料，找到了快慢指针这一概念，就是定义两个指针fast和slow从起点开始，fast每次走两步，slow每次走一步，相遇则说明有环。

• meng：而它们相遇的这个点，一定处于环的内部，并且与头节点的距离是环长度的整数倍记快慢指针相遇的这个点是Xv，一定有v≥μ且v=kλ。于是，寻找环的起点就不难了，因为起点μ一定满足xμ=xμ+v。我们只要从头节点开始遍历链表，第一个满足这个等式的节点就是环的起点。

• 上面的方法就是所谓的Floyd’s cycle-finding algorithm。算法的时间复杂度是O(μ+λ)O(μ+λ)，空间复杂度是O(1)。

• 代码

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
    bool hasCycle(ListNode *head)
    {
        ListNode *fast, *slow;
        fast = slow = head;
        while(fast && fast->next)
        {
            fast = fast -> next -> next;
            slow = slow -> next;
            //快慢指针相遇说明有环
            if(fast == slow)
                return true;
        }
        return false;
    }
};

• （II）思路：如果有环（即isCycle为true），则一个指针从头开始，另一个从xv开始，同时以相同的速度往前移动，每次都移动一步。当两个指针相遇时，位置就是环的起点。

• 代码：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
    bool hasCycle(ListNode *head)
    {
        ListNode *fast, *slow;
        fast = slow = head;
        bool isCycle = false;
        while(fast && fast->next)
        {
            fast = fast -> next -> next;
            slow = slow -> next;
            if(fast == slow)
            {
                isCycle = true;
                break;
            }
        }
        if(isCycle)
        {
            fast = head;
            while(fast != slow)
            {
                fast = fast -> next;
                slow = slow -> next;
            }
            return fast;
        }
        return NULL;
    }
};

另外，如果还要求环的长度（最小正周期），由于已经知道了环的起点，只要从它开始遍历，找到第一个等于起点的位置即可，最多还需要O(λ)的时间。

• 参考

  参考一

  参考二

• 以上。

---

版权声明：本文为博主原创文章，转载请注明出处。 个人博客地址：https://yangyuanlin.club 欢迎来踩~~~~