Solution to LeetCode 142 Linked List Cycle II and LeetCode 160 Intersection of Two Linked Lists.
LeetCode 142
Linked List Cycle II (Medium) [link]
We can use a fast pointer and a slow pointer to determine whether there is a circle. 1) fast pointer moves 2 steps a time, 2) slow pointer moves 1 step a time.
We can find the node where the cycle begins in the similar way:
Let X: distance between the start and the node where the cycle begins, Y: distance between the node where the cycle begins and the point two pointers meet, Z: distance between the node where the two pointers meet and the node where the cycle begins.
The slow pointer goes X+Y. The fast pointer goes X+Y+n(Y+Z). The relationship is (X+Y)*2 = X+Y+n(Y+Z), which is equal to X = n(Y+Z)-Y, then X = (n-1)(Y+Z)+Z. n = 1 then X = Z, they meet when the slow point hasn’t gone into the cycle. n > 1 when fast pointer has to be at least one cycle faster than the slow pointer when they meet.
Q: Why the slow pointer goes X+Y rather than X+Y+a?
A: The slow pointer goes X+Y because the two pointers meet when the slow pointer hasn’t completed the first cycle. Assume the slow point reaches the node where the cycle starts, the fast pointer has to be somewhere in the middle of the cycle, k distance from the node where the cycle starts. Then when the fast pointer reach the node where the cycle starts, it goes k+n, and the slow pointer should go (k+n)/2, where n is the distance of one cycle. Since k<n, (k+n)/2 < n, so the slow pointer has to meet the fast pointer within one cycle.
# 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, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
p = head
q = slow
while q != p:
p = p.next
q = q.next
return p
LeetCode 160
Intersection of Two Linked Lists (Easy) [link]
In this way we make sure a and b move the same distance and end up meeting at the intersect node.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
a, b = headA, headB
while a!=b:
a = a.next if a else headB
b = b.next if b else headA
return a
