In previous posts (Loop in a linked list and Calculate node that causes loop in a linked list) we discussed how to detect loop in a linked list and how to calculate node that causes loop in a linked list. 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 the example
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
