Thursday, December 29, 2011

Calculate length of the linked list that contains loop

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:
looplist1
Dry run the example
Iteration 1:
looplist02
Iteration 2:
looplist12
Iteration 3:
looplist13
Iteration 4:
looplist14 (1)
Iteration 5:
looplist15
From the above it is clear that loop length, L1 is 4.
To calculate length of the list until merging point:
Iteration 1:

looplist16 (1)
Iteration 2:
looplist17
Iteration 3:
looplist18 (1)
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

0 comments:

Post a Comment