Friday, July 4, 2014

Removing a loop in Singly Linked List

Pseudo code: 

1. Two pointers start from head 
2. One pointer advances one while the other advances two. 
3.1 If two pointers meet, there is a loop 
3.2 If pointer reaches the end, there is no loop 
4. Find out how many nodes in the loop, say k. 
5. Reset one pointer to the head, and the other pointer to head + k. 
6. Move both pointers at the same pace, they will meet at loop starting node 
7. Move one pointer till its next node is the loop starting node. It's the loop ending node 
8. Set the next node of the loop ending node to fix the loop 
9. Print the list

No comments:

Post a Comment