Leetcode discuss: 142 Linked List Cycle II

Here is the link.

C# Fast and slow two runners practice on July 14, 2020

July 14, 2020
Introduction

142. Linked List Cycle II

It is common practice to have two runners, one is slow to run one step a time, the fast one is to run two steps a time. If there is a loop in the linked list, then the two runners should meet.

The place to meet in the cycle
Let me mark two places in the linked list, first one is the node position where loop starts, the second one is the place for two runners to meet first time.

Arguments:

1. Fast one and slow should meet definitely, since fast one is behind the slow one, then every unit time the distance will be shorten by one.
2. Define n steps from start to position where loops start denoted LoopStart. Define k step in the loop away from LoopStart meets, LoopMeet. Circle length is denoted as Circle.
3. More one step 2, formula: 2 (n + k) = n + k + Circle, so the distance from
   LoopMeet to LoopStart is same as from beginning to LoopMeet.

Once two runners meet, then move the fast runner to the beginning of linked list, run one step a time to meet the slow runner.

There are three positons, linked list start position, LoopStart, LoopMeet; Two runners, one fast one slow, and we need third runner after slow runner meets fast runner.

Tips
Three positions - three runners - different start time - two start times.

/**
 * 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)
            return null;
        
        var slow = head; 
        var fast = head;
        bool startRace = true; 
        int count = 0; 
        
        while(startRace || slow != fast)
        {
            startRace = false;
            
            slow = slow.next; 
   
   // code is simplified after mock interview
   if(fast.next == null || fast.next.next == null)
   {
    return null;
   }
   
   fast = fast.next.next; 
   
   /*
            fast = fast.next;
            if(fast == null)
            {
                return null; 
            }
            
            fast = fast.next;                        
            
            // duplicate code
            if(fast == null)
            {
                return null; 
            }
            */
            count++; 
        }
        
        // new one starts from head of linked list again, step by step
        // slow one continue
        var newOne = head;
        while(newOne != slow)
        {
            newOne = newOne.next; 
            slow = slow.next; 
        }
        
        return newOne; 
    }
}