codebytes: An algorithm for returning the node at the beginning of a loop in a singly linked list.

codebytes: An algorithm for returning the node at the beginning of a loop in a singly linked list.

Thursday, December 25, 2014 An algorithm for returning the node at the beginning of a loop in a singly linked list. Q. Given a 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 node'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 Methods: #1. Use a Set to record every node that you visit. When a node that is already present in the list is encountered, the is the beginning of the loop. If pointer encounters null, no loop is present. #2. Consider two pointers p1 and p2. p2 travels 2 nodes at a time, p1 travels 1 node at a time. Let them meet (if there is a loop, they will surely meet but if there isn't the fast node will encounter a null). Now that they have met, set p1 to head of the list.  Now let p1 and p2 travel 1 node at a time.

Read full article from codebytes: An algorithm for returning the node at the beginning of a loop in a singly linked list.