R@M3\$H.NBlog

### 17 September, 2013 - 4 min read

In current post we discuss how to calculate length of the linked list when there is a loop in the linked list.

Following procedure explains how to calculate length of the linked list that contains loop:

• Use the standard fast and slow pointer algorithm discussed in previous post to find the loop detection point
• Take two pointers P1 and P2 at loop detection point. Place pointer P1 at the same place and move P2 forward one step at a time. Repeat until both the pointers meet together. Keep a count variable incremented for every iteration which gives length of the loop. Let say the length is L1
• Again take two pointers P1 and P2. P1 at the head of the linked list and P2 at the loop detection point. Forward both the pointers one step at a time. Repeat until both the pointers meet together. This procedure is equivalent to the one we use to calculate node that causes loop in a linked list. Keep a count variable incremented for every iteration which gives the length of the list until the merging point. Let say the length is L2
• Now the length of the list that contains loop is L1+ L2

Consider the following list that contains loop:

Dry run for the above example:

To calculate loop length:

Iteration 1:

Iteration 2:

Iteration 3:

Iteration 4:

Iteration 5:

From the above it is clear that loop length, L1 is 4.

To calculate length of the list until merging point:

Iteration 1:

Iteration 2:

Iteration 3:

From the above it is clear that the length of the loop till merging point, L2 is 2.

Therefore the length of the list that contains loop is L1 + L2 = 4 + 2 = 6

Implementation for class ListNode and class SingleLinkedList is given in the previous post.

Code for the above solution is as follows:

 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 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 `package` `ds;`   `public` `class` `LengthOfLoopedList` `{` `    ``public` `LengthOfLoopedList()` `    ``{` `    ``}`   `    ``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` `int` `getLoopLength(ListNode loopDetectionNode)` `    ``{` `        ``//  Take two pointers at loop detection node and calculate loop length` `        ``ListNode P1 = loopDetectionNode;` `        ``ListNode P2 = loopDetectionNode;`   `        ``int` `loopLength = ``1``;`   `        ``do` `        ``{` `            ``loopLength++;` `            ``P2 = P2.next;` `        ``}``while``(P1 != P2);`   `        ``return` `(loopLength - ``1``);` `    ``}`   `    ``public` `int` `getMergingPointLength(ListNode loopedList, ListNode loopDetectionNode)` `    ``{` `        ``ListNode P1 = loopedList;` `        ``ListNode P2 = loopDetectionNode;`   `        ``//  Calculate length till the merging point` `        ``int` `length = ``1``;` `        ``while``(P1 != P2)` `        ``{` `            ``P1 = P1.next;` `            ``P2 = P2.next;` `            ``length ++;` `        ``}`   `        ``return` `(length - ``1``);` `    ``}`   `    ``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();` `        ``LengthOfLoopedList lengthLoopedList = ``new` `LengthOfLoopedList();`   `        ``//  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 = lengthLoopedList.returnLoopDetectionNode(loopedList);` `        ``int` `loopLength = lengthLoopedList.getLoopLength(loopDetectionNode);` `        ``int` `lengthTillMergingPoint = lengthLoopedList.getMergingPointLength(loopedList, loopDetectionNode);` `        ``int` `lengthOfList = loopLength + lengthTillMergingPoint;`   `        ``System.out.println(``"Length of the linked list that contains a loop is  "``+ lengthOfList);`   `    ``}`   `}`

END