Linked List Cycle Ii

                                            
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head == NULL || head->next == NULL) {
            return NULL;
        }

        ListNode *slow = head;
        ListNode *fast = head;
        bool hasCycle = false;

        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }

        if (!hasCycle) {
            return NULL;
        }

        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }

        return slow;
    }
};

                                            
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        boolean hasCycle = false;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) {
                hasCycle = true;
                break;
            }
        }
        
        if (!hasCycle) {
            return null;
        }
        
        slow = head;
        
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        
        return slow;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *slow = head;
    struct ListNode *fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            struct ListNode *ptr = head;
            while (ptr != slow) {
                ptr = ptr->next;
                slow = slow->next;
            }
            return ptr;
        }
    }

    return NULL;
}

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    public ListNode DetectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                ListNode slow2 = head;
                while (slow2 != slow) {
                    slow = slow.next;
                    slow2 = slow2.next;
                }
                return slow;
            }
        }

        return null;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
var detectCycle = function(head) {
    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) {
            let ptr = head;
            while (ptr !== slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr;
        }
    }

    return null;
};

                                            
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function detectCycle(head: ListNode | null): ListNode | null {
    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next!;
        fast = fast.next.next!;

        if (slow === fast) {
            let slow2 = head;
            while (slow2 !== slow) {
                slow2 = slow2!.next;
                slow = slow!.next;
            }
            return slow2;
        }
    }

    return null;
}

                                            
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) {
 *         $this->val = $val;
 *         $this->next = null;
 *     }
 * }
 */
class Solution {

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function detectCycle($head) {
        $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;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head
    hasCycle := false
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            hasCycle = true
            break
        }
    }
    if !hasCycle {
        return nil
    }
    slow = head
    for slow != fast {
        slow = slow.Next
        fast = fast.Next
    }
    return slow
}

                                            
object Solution {
  def detectCycle(head: ListNode): ListNode = {
    var slow = head
    var fast = head
    var hasCycle = false
    
    while(fast != null && fast.next != null) {
      slow = slow.next
      fast = fast.next.next
      
      if(slow == fast) {
        hasCycle = true
        var ptr = head
        while(ptr != slow) {
          ptr = ptr.next
          slow = slow.next
        }
        return ptr
      }
    }
    
    null
  }
}

To solve this coding challenge, you need to detect the node where a cycle begins in a linked list. This problem requires an understanding of linked lists and specifically the concept of a cycle within them. You need to be able to identify if a cycle exists and where it starts using a two-pointer technique, often referred to as Floyd's Tortoise and Hare algorithm.

Step-by-Step Explanation

Initialize Fast and Slow Pointers:

Two pointers are initialized at the head of the linked list. The

fast

pointer moves twice as fast as the

slow

pointer. This helps in detecting the cycle due to their different speeds.

Find Intersection if Cycle Exists:

Move the

slow

pointer one step and the

fast

pointer two steps at a time. If there is a cycle, they will eventually meet at the same node. If the pointers meet, it confirms the presence of a cycle.

Identify the Start of the Cycle:

To locate the starting node of the cycle, initialize another pointer at the head of the list. Then, move both this new pointer and the

slow

pointer one step at a time. The node where they meet will be the start of the cycle.

Handle No Cycle Scenario:

If the

fast

pointer reaches the end of the list (i.e., it becomes

null

), then there is no cycle in the linked list.

Detailed Steps in Pseudocode

Start by setting the
slow

and
fast

pointers at the head of the linked list.
Traverse the list:

Move
slow

by one step.
Move
fast

by two steps.
Check if
slow

equals
fast

.

If
slow

equals
fast

, there is a cycle:

Initialize a new pointer
cycleStart

at the head of the list.
Move both
cycleStart

and
slow

one step at a time.
When they meet, return that node as it is the starting point of the cycle.

If
fast

reaches
null

or
fast.next

is
null

, return
null

as there is no cycle.

                                            
// Initialize two pointers at the head of the linked list
slowPointer = head
fastPointer = head

// Traverse the linked list to detect cycle
while fastPointer is not null and fastPointer.next is not null:
    // Move slow pointer one step
    slowPointer = slowPointer.next
    // Move fast pointer two steps
    fastPointer = fastPointer.next.next
    
    // Check if both pointers meet
    if slowPointer == fastPointer:
        // Cycle detected, find the start of the cycle
        cycleStart = head
        // Move both pointers one step at a time until they meet
        while cycleStart != slowPointer:
            cycleStart = cycleStart.next
            slowPointer = slowPointer.next
        // Return the start of the cycle
        return cycleStart

// If no cycle is found, return null
return null

Explanation

Initialization : Both
slowPointer

and
fastPointer

are set to the head of the list. This ensures that both start traversing the list from the same point.
Cycle Detection : The
while

loop continues until either the
fastPointer

reaches the end of the list (
fastPointer

or
fastPointer.next

becomes
null

), or the two pointers meet. By moving
slowPointer

by one step and
fastPointer

by two steps, if there's a cycle, they will inevitably meet due to the differing speeds.
Locating the Cycle Start : Once a meeting point is confirmed, initialize another pointer (
cycleStart

) at the head. Move both
cycleStart

and
slowPointer

one step at a time. The point at which they meet is the start of the cycle.
No Cycle : If
fastPointer

reaches
null

, it means there is no cycle, and we return
null

.

This method ensures that we detect a cycle and find the starting node of the cycle using constant space, as required.