C# Fast and slow two runners practice on July 14, 2020
July 14, 2020
Introduction
Introduction
- 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.
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:
- 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.
- 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.
- 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.
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;
}
}
