Linked List Cycle II (M)

題目

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

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

題意

判斷給定鏈表中是否存在環(huán),存在則返回環(huán)的入口結點(diǎn)。

思路

比較簡(jiǎn)單的就是將所有遍歷到的結點(diǎn)記錄下來(lái)，如果記錄了兩次則說(shuō)明當前結點(diǎn)就是所求的結點(diǎn)。

同樣可以使用快慢指針的方法：慢指針每次走一步，快指針每次走兩步，如果快指針追上慢指針則說(shuō)明存在環(huán)；當判斷出存在環(huán)后，將快指針重新指向頭結點(diǎn)，步進(jìn)距離改為一個(gè)結點(diǎn)，然后使快指針和慢指針同時(shí)繼續前進(jìn)，當兩者再次相遇時(shí)，所處結點(diǎn)就是所求入口結點(diǎn)。證明如下：

記第一次相遇時(shí)慢指針走過(guò)的距離為\(S_1\)，快指針走過(guò)的距離為\(S_2\)，那么可得如下方程組：

化簡(jiǎn)后可得：

說(shuō)明當快指針重新從A點(diǎn)走到B點(diǎn)時(shí)，慢指針從C點(diǎn)出發(fā)已經(jīng)走過(guò)了n圈加上z的距離，即也正好落在B點(diǎn)上，因此上述方法能夠正確找到環(huán)的入口結點(diǎn)。

代碼實(shí)現

Java

Hash

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }

        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            if (!set.add(head)) {
                return head;
            }
            head = head.next;
        }

        return null;
    }
}

快慢指針

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }

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

        return null;
    }
}

JavaScript

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  let slow = head
  let fast = head

  while (fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
    if (slow === fast) {
      slow = head
      while (slow !== fast) {
        slow = slow.next
        fast = fast.next
      }
      return slow
    }
  }

  return null
}