Linked List Cycle - Get Node at Intersection

Linked List Cycle - Get Node at Intersection

Coding Solution

·

1 min read

Play this article

Problem

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null. This is similar to the Leetcode Problem - Linked List Cycle II

Approach

The approach would be similar to a linked list cycle, take 2 pointers, slow as turtle and fast as hare. When turtle is equal to hare, the cycle is found. Once the cycle is found, slow will start from head. Both slow and fast will traverse and when they are equal again, that node is the start of the cycle.

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;

        while(fast!=null && fast.next !=null) {
            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;
    }
}

Do have a look at the discuss section for more optimized solutions if available - Linked List Cycle II