Create an account


Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
[Tut] [Floyd’s Algorithm] How to Detect a Cycle in a Linked List in Python?

#1
[Floyd’s Algorithm] How to Detect a Cycle in a Linked List in Python?

In this tutorial you will learn how to implement a simple Python program to detect if a linked list consists of a cycle or not. If you need a brief refresher on linked lists, do check out this blog post



Definition of a Cycle in a Linked List


A linked list can consist of a cycle if a tail node of the linked list points to another node in the list. Let us see a small example to understand the concept of cycle in a linked list.

Definition of a Cycle in a Linked List
Fig 1: Cycle in a linked list

In the above figure, you can see that the tail node of the linked list, instead of pointing to NULL, points to another node — the second node in the list. If such a scenario arises, we say there is a cycle or a loop in a list.

Initialization and Setup


We will first begin by initializing the nodes and constructing the linked list.

from linked_list import Node, LinkedList node1 = Node(5)
node2 = Node(6)
node3 = Node(7)
node4 = Node(8)
node5 = Node(9) ll = LinkedList() ll.insert_back(node1)
ll.insert_back(node2)
ll.insert_back(node3)
ll.insert_back(node4)
ll.insert_back(node5)

Now, we will connect the fifth node to the 3rd node forming a cycle.

node5.next = node3

Approach 1: Naive Approach


We will now look at a simple approach to implement the logic to find out if the list consists of a cycle or not. One approach would be to store the address of the node in a dictionary as we traverse through the list and as soon as we come across a node whose address was already in the dictionary, we can say that there was a cycle in the list. Let us see how we can implement this in Python

 addresses = {}
temp_node = node1
while (temp_node): address = id(temp_node) print(address) if address not in addresses: addresses[address] = 1 else: print('cycle in a linked list') print(temp_node.data) break temp_node = temp_node.next

The disadvantage of the previous approach is that it takes 0(n) space complexity. Can we solve this problem in O(1) space complexity?

Approach 2: Floyd’s Cycle Detection Algorithm


We can solve this problem by initializing two pointers, a slow pointer, and a fast pointer. On every iteration, we increment the slow pointer by 1 and the fast pointer by 2. We then check if the slow pointer is equal to the fast pointer i.e. do both the pointers point to the same node. If that is the case, we can say that there is a cycle or a loop in a linked list. Once we find the cycle we can break out of the while loop

Demonstration

Let us imagine we have a list with 5 nodes as illustrated in the figure below. As you can see the tail node i.e. the node with a value of 9 is pointing to the node with the value 7 or the 3rd node in the list, thereby forming a loop or a cycle.


Iteration 1:  

In the first iteration, the slow pointer is incremented by 1 and the fast pointer by 2. As you can see in the figure below, the slow pointer is now pointing to the node with the value 6 and the fast pointer is pointing to the node with the value 7.


Iteration 2:

In the second iteration  the slow pointer points to the node with the value 7 and the fast pointer points to the node with the value 9 or the last node.


Iteration 3:

In the third iteration we observe that both the slow and fast pointers are pointing to the same  node i.e. the node with the value 8. In this case, we can conclude that there is a cycle in a list.


Let us know see how we can implement the adobe logic in Python.

We first initialize the slow pointer and the fast pointer pointing to the head node or the first node. We then run a while loop, and we run the loop as long as the slow pointer is valid, the fast pointer is valid and the next value of the fast pointer is valid. We then keep incrementing the slow and fast pointers by 1 and 2 respectively and if both the pointers have the same address value, we break out of the loop and print that there was a cycle in a linked list. You can find the entire logic below.

slow_ptr = node1
fast_ptr = node1 while (slow_ptr and fast_ptr and fast_ptr.next): slow_ptr = slow_ptr.next fast_ptr = fast_ptr.next.next if slow_ptr == fast_ptr: print('loop in a linked list', slow_ptr.data) break else: print(slow_ptr.data, fast_ptr.data)

This algorithm is also called the Floyd’s cycle detection algorithm.

Conclusion


In this tutorial, we saw how we can detect a cycle in a loop using the Floyd’s cycle detection algorithm. This algorithm can detect a loop in O(1) space complexity and O(n) time complexity.

The post [Floyd’s Algorithm] How to Detect a Cycle in a Linked List in Python? first appeared on Finxter.



https://www.sickgaming.net/blog/2021/05/...in-python/
Reply



Possibly Related Threads…
Thread Author Replies Views Last Post
  [Tut] Sorting a List Based on Values From Another List xSicKxBot 0 31 04-29-2021, 02:42 PM
Last Post: xSicKxBot
  [Tut] How To Apply A Function To Each Element Of A List? xSicKxBot 0 33 04-25-2021, 07:02 PM
Last Post: xSicKxBot
  [Tut] How to Convert a String List to an Integer List in Python xSicKxBot 0 43 04-09-2021, 01:50 PM
Last Post: xSicKxBot
  [Tut] How to Convert a Float List to a String List in Python xSicKxBot 0 42 04-07-2021, 02:53 PM
Last Post: xSicKxBot
  [Tut] Check If All Elements In A List Are Identical xSicKxBot 0 54 03-20-2021, 10:12 AM
Last Post: xSicKxBot
  [Tut] How to Loop Through a Python List in Pairs, Sliding Windows, and Batches? xSicKxBot 0 50 03-17-2021, 03:08 PM
Last Post: xSicKxBot
  [Tut] How to Create a Tuple from a String and a List of Strings xSicKxBot 0 53 03-13-2021, 09:55 AM
Last Post: xSicKxBot
  [Tut] How to Replace One or More List Elements at Specific Indices in Python? xSicKxBot 0 57 03-09-2021, 05:03 PM
Last Post: xSicKxBot
  [Tut] How to Check if an Object is of Type List in Python? xSicKxBot 0 79 02-09-2021, 08:05 AM
Last Post: xSicKxBot
  [Tut] How to Get map() to Return a List in Python 3.x xSicKxBot 0 90 01-23-2021, 08:23 PM
Last Post: xSicKxBot

Forum Jump:

[-]
Active Threads
(Indie Deal) God Eater 3, DRAGON BALL, T...
Last Post: xSicKxBot
Today 10:20 AM
» Replies: 0
» Views: 6
Microsoft - Making remote and hybrid mee...
Last Post: xSicKxBot
Today 05:33 AM
» Replies: 0
» Views: 7
News - JAVA EDITION: SNAPSHOT 21W19A
Last Post: xSicKxBot
Today 05:31 AM
» Replies: 0
» Views: 7
News - Koei Tecmo’s Guzzler Joins Hamste...
Last Post: xSicKxBot
Today 05:30 AM
» Replies: 0
» Views: 8
News - Sega Looking To Release Brand New...
Last Post: xSicKxBot
Today 05:30 AM
» Replies: 0
» Views: 7
Xbox Wire - Xbox Spotlight: Mental Healt...
Last Post: xSicKxBot
Today 05:30 AM
» Replies: 0
» Views: 7
News - Live services push EA to $6.19 bi...
Last Post: xSicKxBot
Today 05:29 AM
» Replies: 0
» Views: 48
News - Blog: Improving the ‘About This G...
Last Post: xSicKxBot
Today 05:29 AM
» Replies: 0
» Views: 44
[Tut] How to Check the Pandas Version in...
Last Post: xSicKxBot
Yesterday 08:38 PM
» Replies: 0
» Views: 8
(Indie Deal) NBA 2K21, MY HERO ONE'S JUS...
Last Post: xSicKxBot
Yesterday 08:37 PM
» Replies: 0
» Views: 6

[-]
Twitter

Copyright © SickGaming.net 2012-2020