Detect loop in a linked list ?
- Traverse through each node till end , tracking visited node using Hash map.
- If you find node that is already visited, then there is a loop in LinkedList
- If you reach till end while traversing then there is no loop in LinkedList
[pastacode lang=”markdown” manual=”using%20namespace%20std%3B%20%0A%0Astruct%20Node%20%0A%7B%20%0A%09int%20data%3B%20%0A%09struct%20Node*%20next%3B%20%0A%7D%3B%20%0A%0Avoid%20push(struct%20Node**%20head_ref%2C%20int%20new_data)%20%0A%7B%20%0A%0A%09struct%20Node*%20new_node%20%3D%20new%20Node%3B%20%0A%0A%09%0A%09new_node-%3Edata%20%3D%20new_data%3B%20%0A%0A%09%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%09new_node-%3Enext%20%3D%20(*head_ref)%3B%20%0A%0A%09%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%09(*head_ref)%20%3D%20new_node%3B%20%0A%7D%20%0A%0A%2F%2F%20Returns%20true%20if%20there%20is%20a%20loop%20in%20linked%20list%20%0A%2F%2F%20else%20returns%20false.%20%0Abool%20detectLoop(struct%20Node%20*h)%20%0A%7B%20%0A%09unordered_set%3CNode%20*%3E%20s%3B%20%0A%09while%20(h%20!%3D%20NULL)%20%0A%09%7B%20%0A%09%09%2F%2F%20If%20this%20node%20is%20already%20present%20%0A%09%09%2F%2F%20in%20hashmap%20it%20means%20there%20is%20a%20cycle%20%0A%09%09%2F%2F%20(Because%20you%20we%20encountering%20the%20%0A%09%09%2F%2F%20node%20for%20the%20second%20time).%20%0A%09%09if%20(s.find(h)%20!%3D%20s.end())%20%0A%09%09%09return%20true%3B%20%0A%0A%09%09%2F%2F%20If%20we%20are%20seeing%20the%20node%20for%20%0A%09%09%2F%2F%20the%20first%20time%2C%20insert%20it%20in%20hash%20%0A%09%09s.insert(h)%3B%20%0A%0A%09%09h%20%3D%20h-%3Enext%3B%20%0A%09%7D%20%0A%0A%09return%20false%3B%20%0A%7D%20%0A%0A%2F*%20Drier%20program%20to%20test%20above%20function*%2F%0Aint%20main()%20%0A%7B%20%0A%09%2F*%20Start%20with%20the%20empty%20list%20*%2F%0A%09struct%20Node*%20head%20%3D%20NULL%3B%20%0A%0A%09push(%26head%2C%2021)%3B%20%0A%09push(%26head%2C%2014)%3B%20%0A%09push(%26head%2C%205)%3B%20%0A%09push(%26head%2C%2010)%3B%20%0A%0A%09%2F*%20Create%20a%20loop%20for%20testing%20*%2F%0A%09head-%3Enext-%3Enext-%3Enext-%3Enext%20%3D%20head%3B%20%0A%0A%09if%20(detectLoop(head))%20%0A%09%09cout%20%3C%3C%20%22Loop%20found%22%3B%20%0A%09else%0A%09%09cout%20%3C%3C%20%22No%20Loop%22%3B%20%0A%0A%09return%200%3B%20%0A%7D%20″ message=”” highlight=”” provider=”manual”/]
- Efficient approach for this problem would be Floyd’s cycle detection algorithm, so steps for this algorithm would be:
-
- Use two pointer fastPtr and slowPtr and initialize both to head of linkedlist
- Move fastPtr by two nodes and slowPtr by one node in each iteration.
- If fastPtr and slowPtr meet at some iteration , then there is a loop in linkedlist.
- If fastPtr reaches to the end of linkedlist without meeting slow pointer then there is no loop in linkedlist (i.e fastPtr->next or fastPtr->next->next become null).
[pastacode lang=”c” manual=”%2F%2F%20C%20program%20to%20detect%20loop%20in%20a%20linked%20list%20%0A%23include%3Cstdio.h%3E%20%0A%23include%3Cstdlib.h%3E%20%0A%2F*%20Link%20list%20node%20*%2F%0Astruct%20Node%20%0A%7B%20%0A%09int%20data%3B%20%0A%09struct%20Node*%20next%3B%20%0A%7D%3B%20%0A%0Avoid%20push(struct%20Node**%20head_ref%2C%20int%20new_data)%20%0A%7B%20%0A%09%2F*%20allocate%20node%20*%2F%0A%09struct%20Node*%20new_node%20%3D%20%0A%09%09(struct%20Node*)%20malloc(sizeof(struct%20Node))%3B%20%0A%0A%09%2F*%20put%20in%20the%20data%20*%2F%0A%09new_node-%3Edata%20%3D%20new_data%3B%20%0A%0A%09%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%09new_node-%3Enext%20%3D%20(*head_ref)%3B%20%0A%0A%09%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%09(*head_ref)%20%3D%20new_node%3B%20%0A%7D%20%0A%0Aint%20detectloop(struct%20Node%20*list)%20%0A%7B%20%0A%09struct%20Node%20*slow_p%20%3D%20list%2C%20*fast_p%20%3D%20list%3B%20%0A%0A%09while%20(slow_p%20%26%26%20fast_p%20%26%26%20fast_p-%3Enext%20)%20%0A%09%7B%20%0A%09%09slow_p%20%3D%20slow_p-%3Enext%3B%20%0A%09%09fast_p%20%3D%20fast_p-%3Enext-%3Enext%3B%20%0A%09%09if%20(slow_p%20%3D%3D%20fast_p)%20%0A%09%09%7B%20%0A%09%09printf(%22Found%20Loop%22)%3B%20%0A%09%09return%201%3B%20%0A%09%09%7D%20%0A%09%7D%20%0A%09return%200%3B%20%0A%7D%20%0A%0A%2F*%20Drier%20program%20to%20test%20above%20function*%2F%0Aint%20main()%20%0A%7B%20%0A%09%2F*%20Start%20with%20the%20empty%20list%20*%2F%0A%09struct%20Node*%20head%20%3D%20NULL%3B%20%0A%0A%09push(%26head%2C%2010)%3B%20%0A%09push(%26head%2C%204)%3B%20%0A%09push(%26head%2C%205)%3B%20%0A%09push(%26head%2C%2010)%3B%20%0A%0A%09%2F*%20Create%20a%20loop%20for%20testing%20*%2F%0A%09head-%3Enext-%3Enext-%3Enext-%3Enext%20%3D%20head%3B%20%0A%09detectloop(head)%3B%20%0A%0A%09return%200%3B%20%0A%7D” message=”” highlight=”” provider=”manual”/]
