Q142. Linked List Cycle II

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Notice that you should not modify the linked list.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

 

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.
 

Constraints:

The number of the nodes in the list is in the range [0, 104].
-105 <= Node.val <= 105
pos is -1 or a valid index in the linked-list.

This question is quite challenging for me. I did not come up with the idea .. It turns out that we need two pointers to do the trick. I feel that it is somewhat clever and fit the question just well.

To solve the question essentially contains two steps:

1. Identify if there is loop.
2. If so, identify the node which has two incoming edges.

The first step is “Q141. Linked List Cycle”. (If I was given this question, I could not get it, either ..) The trick is to use two pointers which have different speeds. Specifically, let’s have two pointers, slow and fast, where fast goes twice as fast as slow.

Then, we can image that:

• If there is no loop, fast will hit None eventually and we can terminate safely.
• If there is loop, fast and slow will meet eventually. And suppose the algorithm goes for n steps when they meet, then fast goes n steps more than slow and n is actually the length of (or the multiple of it) the loop.

OK, here comes to the second part: How to identify the “bad” node (where the loop “start”)? If the length between the head node and the “bad” node is L, then we want the fast node to go extra L step to hit the “bad” node (since it already goes 2n - L steps in the loop and need L extra steps to be the multiple of loop size). We could implement so by sending slow to the head node and let slow and fast move in the same speed. By doing so, they will met at the “bad” node since after L steps, slow also appears at the “bad” node.

The Python submission.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow = head
        fast = head
        # fast is twice as fast as slow
        while fast is not None and fast.next is not None:
            fast = fast.next.next
            slow = slow.next
            if fast is not None and slow == fast:
                break
        # print(slow.val, fast.val)
        if fast is None or fast.next is None:
            return None
        slow = head
        while fast != slow:
            fast = fast.next
            slow = slow.next
            # print(slow.val, fast.val)
        return slow