Linked List Cycle II

Leetcode Daily Challenge (9th March, 2023)

9 March, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

Problem Statement:-

Given the head of 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 (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Link: https://leetcode.com/problems/linked-list-cycle-ii/

Problem Explanation with examples:-

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, 10^4].
-10^5 <= Node.val <= 10^5
pos is -1 or a valid index in the linked-list.

Intuition:-

As we know this is a famous problem, we can use the floyd cycle detection algorithm to solve this problem.
We can use two pointers, one is slow, and the other is fast.
We can use the fast pointer to move two steps, and the slow pointer to move one step.
If there is a cycle, the fast pointer will meet the slow pointer.
If there is no cycle, the fast pointer will meet the end of the linked list.
After we find the meeting point, we can use the slow pointer to move one step, and the fast pointer to move one step.
When the slow pointer and the fast pointer meet, we can return the slow pointer as the start of the cycle.

Solution:-

Initialize the slow pointer and the fast pointer to the head of the linked list.slow = head fast = head
Run a while loop, if the fast pointer and the fast pointer.next is not None, we can move the slow pointer one step, and the fast pointer two steps.
If the slow pointer and the fast pointer meet, we can break the loop. This means we detected the cycle.
If the fast pointer and the fast pointer.next is None, we can return None as there is no cycle.while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: break else: return None
After we detect the cycle, we can initialize the slow pointer to the head of the linked list.
Run a while loop, if the slow pointer and the fast pointer are not equal, we can move the slow pointer one step, and the fast pointer one step as well.

When the slow pointer and the fast pointer are equal, we can return the slow pointer or the fast pointer as the start of the cycle.

slow = head
while slow != fast:
    slow = slow.next
    fast = fast.next

return fast

Code:-

JAVA Solution

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

Python Solution

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break
        else:
            return None
        
        slow = head
        while slow != fast:
            slow = slow.next
            fast = fast.next

        return fast

Complexity Analysis:-

TIME:-

Time complexity is O(n), as we only need to run one loop for increasing the slow pointer and the fast pointer.

SPACE:-

Space complexity is O(1), as we only need to use two pointers.