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:
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
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
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
0 comments:
Post a Comment