CC150 – 2.6 Looped Linked List

Given an circular linked list, implement an algorithm which returns the node at
the beginning of the loop.

DEFINITION
Circular linked list: A (corrupt) linked list in which a nodes’s next pointer points
to an earlier node, so as to make a loop in the linked list;
EXAMPLE
Input: A -> B -> C -> D -> E -> C [the same C as earlier]
Output: C

20140406_153636


The general way to solve a looped linked list is using 2 iterators – fastRunner & slowRunner. fastRunner goes at 2 step/time, slowRunner goes

\cos (2\theta) = \cos^2 \theta - \sin^2 \theta

 

Author: Jerry Wu

Keep moving forward!

Leave a comment