R@M3\$H.NBlog

# [Linked List] Find Loop Node

### 17 September, 2013 - 3 min read

In this post we will discuss how to find the node that causes loop in linked list.

Following procedure explains on how to detect node that caused loop:

• By following the procedure described in previous post (Slow pointer and fast pointer approach),  we found the loop detection node
• Now take pointers P1 and P2, P1 at the loop detection node and P2 starting from head of the linked list
• Traverse both the pointers one at a time
• Both the pointers meet at the node because of which there is a loop in the linked list

For example consider the following linked list where the loop is detected at node 5:

Dry run for the above example:

Take two pointers P1 and P2 pointing to node 1(head of the linked list) and node 5(loop detection point) respectively.

Iteration 1:

Iteration 2:

Iteration 3:

Here both of them meet at node that contains data as 3. Hence the node that causes loop in a linked list is node 3.

The following program finds out the node that causes loop:

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 `package` `ds;` `public` `class` `MergePointInLoopedList ` `{` `    ``public` `MergePointInLoopedList()` `    ``{` `    ``}` `    ` `    ``public` `ListNode returnLoopDetectionNode(ListNode loopedList)` `    ``{` `        ``ListNode fastNode = loopedList;` `        ``ListNode slowNode = loopedList;` `        ` `        ``while``(fastNode.next.next != ``null``)` `        ``{` `            ``slowNode = slowNode.next;` `            ``fastNode = fastNode.next.next;` `            ` `            ``if``(slowNode == fastNode)` `            ``{` `                ``break``;` `            ``}` `        ``}` `        ` `        ``return` `slowNode;` `    ``}` `    ` `    ``public` `static` `void` `main(String[] args)` `    ``{` `        ``SingleLinkedList newList = ``new` `SingleLinkedList();` `        ``newList.add(``1``);` `        ``newList.add(``2``);` `        ``ListNode loopNode = newList.add(``3``);` `        ``newList.add(``4``);` `        ``newList.add(``5``);` `        ``ListNode endNode = newList.add(``6``);` `        ``//  Creating a loop` `        ``endNode.next = loopNode;` `        ` `        ``ListNode loopedList = newList.getList();` `        ``MergePointInLoopedList mergePointLoopedList = ``new` `MergePointInLoopedList();` `        ``//  Assuming there is a loop in linked list and finding loop detection node` `        ``//  Loop detection node is the one where slow pointer and fast pointer meet` `        ``ListNode loopDetectionNode = mergePointLoopedList.returnLoopDetectionNode(loopedList);` `        ` `        ``//  Now take pointers P1 and P2. Let P2 be at loop detection node and P1 be at the head` `        ``// of the looped linked list` `        ` `        ``ListNode P1 = loopedList;` `        ``ListNode P2 = loopDetectionNode;` `        ` `        ``while``(P1 != P2)` `        ``{` `            ``P1 = P1.next;` `            ``P2 = P2.next;` `        ``}` `        ` `        ``System.out.println(``"Merging point in linked list that has a loop is ... "``+ P1.data);` `   ``}` `}`

END