• 591 views

How to detect a cycle in a linked list ?

Answer : A linked list is said to contain a cycle …
Total
0
Shares
0
0
0
0

How to detect a cycle in a linked list ?

  • A linked list is said to contain a cycle if any node is visited more than once.
How do you detect a cycle in a linked list

Method 1 – Using Hashing

  • Traverse the given list.
  • Insert each encountered node into a hash table.
  • If the current already present ,that means the cycle is present or not.

Sample code

[pastacode lang=”java” manual=”%23include%20%3Ciostream%3E%0A%23include%20%3Cunordered_set%3E%0Ausing%20namespace%20std%3B%0A%0A%2F%2F%20Data%20Structure%20to%20store%20a%20linked%20list%20node%0Astruct%20Node%0A%7B%0A%20%20%20%20int%20dt%3B%0A%20%20%20%20Node*%20next%3B%0A%7D%3B%0A%0A%2F%2F%20Helper%20function%20to%20create%20a%20new%20node%20with%20the%20given%20data%20and%0A%2F%2F%20pushes%20it%20onto%20the%20front%20of%20the%20list%0Avoid%20push(Node*%26%20headRef%2C%20int%20dt)%0A%7B%0A%20%20%20%20%2F%2F%20create%20a%20new%20linked%20list%20node%20from%20heap%0A%20%20%20%20Node*%20newNode%20%3D%20new%20Node%3B%0A%0A%20%20%20%20newNode-%3Edt%20%3D%20dt%3B%0A%20%20%20%20newNode-%3Enext%20%3D%20headRef%3B%0A%20%20%20%20headRef%20%3D%20newNode%3B%0A%7D%0A%0A%2F%2F%20Function%20to%20detect%20Cycle%20in%20a%20linked%20list%20using%20Hashing%0Abool%20detectcyc(Node%20*head)%0A%7B%0A%20%20%20%20Node%20*current%20%3D%20head%3B%0A%20%20%20%20unordered_set%3CNode*%3E%20set%3B%0A%0A%20%20%20%20%2F%2F%20traverse%20the%20list%0A%20%20%20%20while%20(current)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20return%20false%20if%20we%20already%20have%20seen%20this%20node%20before%0A%20%20%20%20%20%20%20%20if%20(set.find(current)%20!%3D%20set.end())%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%0A%20%20%20%20%20%20%20%20%2F%2F%20insert%20current%20node%20into%20the%20set%0A%20%20%20%20%20%20%20%20set.insert(current)%3B%0A%0A%20%20%20%20%20%20%20%20%2F%2F%20move%20to%20the%20next%20node%0A%20%20%20%20%20%20%20%20current%20%3D%20current-%3Enext%3B%0A%20%20%20%20%7D%0A%0A%20%20%20%20%2F%2F%20we%20reach%20here%20if%20list%20does%20not%20contain%20any%20cycle%0A%20%20%20%20return%20false%3B%0A%7D%0A%0A%2F%2F%20Detect%20Cycle%20in%20a%20linked%20list%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20input%20keys%0A%20%20%20%20int%20k%5B%5D%20%3D%20%7B%201%2C%202%2C%203%2C%204%2C%205%20%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(k)%20%2F%20sizeof(k%5B0%5D)%3B%0A%0A%20%20%20%20Node*%20head%20%3D%20nullptr%3B%0A%20%20%20%20for%20(int%20i%20%3D%20n%20-%201%3B%20i%20%3E%3D%200%3B%20i–)%0A%20%20%20%20%20%20%20%20push(head%2C%20k%5Bi%5D)%3B%0A%0A%20%20%20%20%2F%2F%20insert%20cycle%0A%20%20%20%20head-%3Enext-%3Enext-%3Enext-%3Enext-%3Enext%20%3D%20head-%3Enext-%3Enext%3B%0A%0A%20%20%20%20if%20(detectcyc(head))%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22Cycle%20Found%22%3B%0A%20%20%20%20else%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22No%20Cycle%20Found%22%3B%0A%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/]

Output

Cycle Found

Method 2 – Floyd’s Cycle Detection Algorithm

  • Use two pointers, which move through the sequence at different speed.
  • The fast pointer moves twice as quickly as the slow pointer.
  • Here the distance between the two pointers increased by 1 at each step.
  • If these pointers meet at same node then there is a loop else linked list doesn’t have loop.

Sample Code

[pastacode lang=”java” manual=”%23include%20%3Ciostream%3E%0A%23include%20%3Cunordered_set%3E%0Ausing%20namespace%20std%3B%0A%0A%2F%2F%20Data%20Structure%20to%20store%20a%20linked%20list%20node%0Astruct%20Node%0A%7B%0A%20%20%20%20int%20dt%3B%0A%20%20%20%20Node*%20next%3B%0A%7D%3B%0A%0A%2F%2F%20Helper%20function%20to%20create%20a%20new%20node%20with%20the%20given%20data%20and%0A%2F%2F%20pushes%20it%20onto%20the%20front%20of%20the%20list%0Avoid%20push(Node*%26%20headRef%2C%20int%20dt)%0A%7B%0A%20%20%20%20%2F%2F%20create%20a%20new%20linked%20list%20node%20from%20heap%0A%20%20%20%20Node*%20nNode%20%3D%20new%20Node%3B%0A%0A%20%20%20%20nNode-%3Edt%20%3D%20dt%3B%0A%20%20%20%20nNode-%3Enext%20%3D%20headRef%3B%0A%20%20%20%20headRef%20%3D%20nNode%3B%0A%7D%0A%0A%2F%2F%20Function%20to%20detect%20Cycle%20in%20a%20linked%20list%20using%0A%2F%2F%20Floyd%E2%80%99s%20Cycle%20Detection%20Algorithm%0Abool%20dcycle(Node%20*head)%0A%7B%0A%20%20%20%20%2F%2F%20take%20two%20pointers%20-%20slow%20and%20fast%0A%20%20%20%20Node%20*slow%20%3D%20head%2C%20*fast%20%3D%20head%3B%0A%0A%20%20%20%20while%20(fast%20%26%26%20fast-%3Enext)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20move%20slow%20by%20one%20pointer%0A%20%20%20%20%20%20%20%20slow%20%3D%20slow-%3Enext%3B%0A%0A%20%20%20%20%20%20%20%20%2F%2F%20move%20fast%20by%20two%20pointers%0A%20%20%20%20%20%20%20%20fast%20%3D%20fast-%3Enext-%3Enext%3B%0A%0A%20%20%20%20%20%20%20%20%2F%2F%20if%20they%20meet%20any%20any%20node%2C%20linked%20list%20contains%20a%20cycle%0A%20%20%20%20%20%20%20%20if%20(slow%20%3D%3D%20fast)%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%7D%0A%0A%20%20%20%20%2F%2F%20we%20reach%20here%20if%20slow%20%26%20fast%20pointer%20do%20not%20meet%0A%20%20%20%20return%20false%3B%0A%7D%0A%0A%2F%2F%20Detect%20Cycle%20in%20a%20linked%20list%20using%20Floyd%E2%80%99s%20Cycle%20Detection%20Algorithm%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20input%20keys%0A%20%20%20%20int%20k%5B%5D%20%3D%20%7B%201%2C%202%2C%203%2C%204%2C%205%20%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(k)%20%2F%20sizeof(k%5B0%5D)%3B%0A%0A%20%20%20%20Node*%20head%20%3D%20nullptr%3B%0A%20%20%20%20for%20(int%20i%20%3D%20n%20-%201%3B%20i%20%3E%3D%200%3B%20i–)%0A%20%20%20%20%20%20%20%20push(head%2C%20k%5Bi%5D)%3B%0A%0A%20%20%20%20%2F%2F%20insert%20cycle%0A%20%20%20%20head-%3Enext-%3Enext-%3Enext-%3Enext-%3Enext%20%3D%20head-%3Enext-%3Enext%3B%0A%0A%20%20%20%20if%20(dcycle(head))%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22Cycle%20Found%22%3B%0A%20%20%20%20else%0A%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22No%20Cycle%20Found%22%3B%0A%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/]

Output

Cycle Found
Related Tags
Leave a Reply

Your email address will not be published. Required fields are marked *

You May Also Like