[算法][LeetCode]Linked List Cycle & Linked List Cycle II――单链表中的环 - 南京大乱炖 - 博客园

[算法][LeetCode]Linked List Cycle & Linked List Cycle II――单链表中的环 - 南京大乱炖 - 博客园

Linked List Cycle

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?
如何找到环的第一个节点？

1. 环的长度是多少？

2. 如何找到环中第一个节点（即Linked List Cycle II）？

3. 如何将有环的链表变成单链表（解除环）？

4. 如何判断两个单链表是否有交点？如何找到第一个相交的节点？

设：链表头是X，环的第一个节点是Y，slow和fast第一次的交点是Z。各段的长度分别是a,b,c，如图所示。环的长度是L。slow和fast的速度分别是qs,qf。

下面我们来挨个问题分析。

1. 方法一（网上都是这个答案）：

第一次相遇后，让slow,fast继续走，记录到下次相遇时循环了几次。因为当fast第二次到达Z点时，fast走了一圈，slow走了半圈，而当fast第三次到达Z点时，fast走了两圈，slow走了一圈，正好还在Z点相遇。

方法二：

第一次相遇后，让fast停着不走了，slow继续走，记录到下次相遇时循环了几次。

方法三（最简单）：

第一次相遇时slow走过的距离：a+b，fast走过的距离：a+b+c+b。

因为fast的速度是slow的两倍，所以fast走的距离是slow的两倍，有 2(a+b) = a+b+c+b，可以得到a=c（这个结论很重要！）。

我们发现L=b+c=a+b，也就是说，从一开始到二者第一次相遇，循环的次数就等于环的长度。

2. 我们已经得到了结论a=c，那么让两个指针分别从X和Z开始走，每次走一步，那么正好会在Y相遇！也就是环的第一个节点。

3. 在上一个问题的最后，将c段中Y点之前的那个节点与Y的链接切断即可。

4. 如何判断两个单链表是否有交点？先判断两个链表是否有环，如果一个有环一个没环，肯定不相交；如果两个都没有环，判断两个列表的尾部是否相等；如果两个都有环，判断一个链表上的Z点是否在另一个链表上。

如何找到第一个相交的节点？求出两个链表的长度L1,L2（如果有环，则将Y点当做尾节点来算），假设L1<L2，用两个指针分别从两个链表的头部开始走，长度为L2的链表先走(L2-L1)步，然后两个一起走，直到二者相遇。

public static ListNode detectCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while (true) {
        if (fast == null || fast.next == null) {
            return null;    //遇到null了，说明不存在环
        }
        slow = slow.next;
        fast = fast.next.next;
        if (fast == slow) {
            break;    //第一次相遇在Z点
        }
    }

    slow = head;    //slow从头开始走，
    while (slow != fast) {    //二者相遇在Y点，则退出
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}

https://leetcode.com/problems/linked-list-cycle-ii/discuss/44774/Java-O(1)-space-solution-with-detailed-explanation.

Define two pointers slow and fast. Both start at head node, fast is twice as fast as slow. If it reaches the end it means there is no cycle, otherwise eventually it will eventually catch up to slow pointer somewhere in the cycle.

Let the distance from the first node to the the node where cycle begins be A, and let say the slow pointer travels travels A+B. The fast pointer must travel 2A+2B to catch up. The cycle size is N. Full cycle is also how much more fast pointer has traveled than slow pointer at meeting point.

A+B+N = 2A+2B
N=A+B

From our calculation slow pointer traveled exactly full cycle when it meets fast pointer, and since originally it travled A before starting on a cycle, it must travel A to reach the point where cycle begins! We can start another slow pointer at head node, and move both pointers until they meet at the beginning of a cycle

            public ListNode detectCycle(ListNode head) {
                ListNode slow = head;
                ListNode fast = head;
        
                while (fast!=null && fast.next!=null){
                    fast = fast.next.next;
                    slow = slow.next;
                    
                    if (fast == slow){
                        ListNode slow2 = head; 
                        while (slow2 != slow){
                            slow = slow.next;
                            slow2 = slow2.next;
                        }
                        return slow;
                    }
                }
                return null;
            }

http://blog.csdn.net/kenden23/article/details/13871699

Boolean: HasLoopHashTable(Cell: sentinel) // Make a hash table. Hashtable: visited // Loop through the list. Cell: cell = sentinel While (cell.Next != null) // See if we already visited the next cell. If (visited.Contains(cell.Next)) // This is the start of a loop. // Break the loop and return true. cell.Next = null Return true End If // Add the cell to the hash table. visited.Add(cell) // Move to the next cell. cell = cell.Next End While // If we get this far, there is no loop. Return false End HasLoopHashTable

LIST RETRACING - O(n^2)
This algorithm makes an object traverse the list. For each cell visited, the algorithm makes a second object traverse the list until it finds the first object. If the cells before the two objects are different, then the list contains a loop.
// Return true if the list has a loop. // If the list has a loop, break it. Boolean: HasLoopRetracing(Cell: sentinel) // Loop through the list. Cell: cell = sentinel While (cell.Next != null) // See if we already visited the next cell. Cell: tracer = sentinel While (tracer != cell) If (tracer.Next == cell.Next) // This is the start of a loop. // Break the loop and return true. cell.Next = null Return true End If tracer = tracer.Next End While // Move to the next cell. cell = cell.Next End While // If we get here, the list has no loop. Return false End HasLoopRetracing

LIST REVERSAL
This algorithm traverses the list, reversing each cell's link so that it points to the cell before it in the list instead of the one after it. If the algorithm reaches the list's sentinel, the list contains a loop. If the algorithm reaches a null link without reaching the sentinel, the list doesn't contain a loop.

Of course, moving through the list reversing links messes up the links. To restore them, the algorithm then moves back through the list a second time, reversing the links again so that they point to where they did originally.

// Reverse the loop once and return the new top of the list. Cell: ReverseList(Cell: sentinel) Cell: prev_cell = null Cell: curr_cell = sentinel While (curr_cell != null) // Reverse the link out of this cell. Cell: next_cell = curr_cell.Next curr_cell.Next = prev_cell // Move to the next cell. prev_cell = curr_cell curr_cell = next_cell End While // Return the last cell we visited. Return prev_cell End ReverseList

// Return true if the list has a loop. Boolean: HasLoopReversing(Cell: sentinel) { // If the list is empty, it has no loops. If (sentinel.Next == null) Then Return false // Loop through the list, reversing links. Cell: new_sentinel = ReverseList(sentinel) // Loop through the list again to restore the links. ReverseList(new_sentinel) // If the reversed list starts with the same cell // as the original list, there is a loop. // Return the result. If (new_sentinel == sentinel) Then Return true Return false End HasLoopReversing

LOOPS IN DOUBLY LINKED LISTS
Detecting loops in a doubly linked list is easy. If there is a loop, somewhere a Next pointer jumps back to an earlier part of the list. The Prev pointer in that cell points to an earlier cell, not the one that created the loop.

So, to detect a loop, simply traverse the list, and for each cell, verify that cell. Next.Prev == cell.

This all assumes that the cells form a normal doubly linked list and that a loop, if it exists, is a simple loop. If the Next and Prev lists are completely out of sync, this method detects the mess but doesn't help you fix it. This is more a case of two threads through the same cells than a doubly linked list with a loop.
https://leetcode.com/articles/linked-list-cycle/

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

  public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
      return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
      if (fast == null || fast.next == null) {
        return false;
      }
      slow = slow.next;
      fast = fast.next.next;
    }
    return true;
  }

Read full article from [算法][LeetCode]Linked List Cycle & Linked List Cycle II――单链表中的环 - 南京大乱炖 - 博客园