R@M3$H.NBlog

[Linked List] Find Length of Linked List that contains Loop

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