Linked List Cycle Ii - Leetcode Solution

The Linked List Cycle II problem on LeetCode is a popular problem in the field of data structures and algorithms. It focuses on the concept of linked lists and cycling, and the goal is to detect if there is a cycle in a linked list and return the node at which the cycle begins.

Problem statement

Given a linked list, determine if it has a cycle in it. To represent a cycle in the 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.

Example

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.

Solution

The problem can be solved using the concept of the two-pointer approach. We can have two pointers, one moving at a slow pace and the other moving at a fast pace. If there is a cycle in the list, then eventually, the fast pointer will catch up with the slow pointer, and they will meet at a node within the cycle. We can then return the node at which the cycle begins.

The following is the algorithm to solve the problem:

1. Initialize two pointers, slow and fast, both pointing to the head of the linked list.
2. Move the slow pointer by one step and the fast pointer by two steps.
3. Continue this process until the fast pointer encounters a null node or a node pointing to the head of the linked list.
4. If the fast pointer reaches a null node, then there is no cycle in the list, and we can return null.
5. If the fast pointer reaches a node pointing to the head of the list, then the list has a cycle, and we can return the head node as the start of the cycle.
6. If the fast pointer encounters the slow pointer while traversing the list, then there is a cycle, and we can return the node where the cycle begins.

The following is the Python implementation of the above algorithm:

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def detectCycle(head: ListNode) -> ListNode:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if fast == slow:
            while head != slow:
                head = head.next
                slow = slow.next
            return head
    return None

In the above implementation, we first initialize the slow and fast pointers to the head of the linked list. We then loop through the list, moving the slow pointer by one step and the fast pointer by two steps. If there is no cycle in the list, the fast pointer will eventually reach the end, and the loop will end. We then return null as there is no cycle.

If there is a cycle, then there is a point where the fast pointer will encounter the slow pointer while traversing the list. We then move the head pointer and the slow pointer by one step until they meet. We do this because the head and the slow pointer are k steps away from each other, where k is the distance from the head to the start of the cycle. By moving them both by one step at a time, they will eventually meet at the beginning of the cycle. We then return the head node as the start of the cycle.

Conclusion

The Linked List Cycle II problem on LeetCode is a popular problem in the field of data structures and algorithms. It can be solved using the two-pointer approach, and the Python implementation of the solution is simple and easy to understand.

1