Python Program to Detect Cycle in a Linked List

This is a Python program to check whether a linked list has a cycle.

The program creates a linked list using data items input from the user and determines whether it has a cycle.

1. Create a class Node with instance variables data and next.
2. Create a class LinkedList with instance variables head and last_node.
3. The variable head points to the first element in the linked list while last_node points to the last.
4. Define methods append and display inside the class LinkedList to append data and display the linked list respectively.
5. Define method get_node which takes an index as argument and returns the node at that index.
6. Define a function has_cycle which returns True if the linked list has a cycle.
7. The function has_cycle uses the Floyd’s cycle-finding algorithm.
8. In this algorithm, one pointer traverses the list one node at a time while another pointer traverses it two nodes at a time. If the two pointers equal before the faster pointer reaches None, then the list has a cycle.
9. Create an instance of LinkedList, append data to it and determine whether it has a cycle.

Here is the source code of a Python program to check whether a linked list has a cycle.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
class LinkedList:
    def __init__(self):
        self.head = None
        self.last_node = None
 
    def append(self, data):
        if self.last_node is None:
            self.head = Node(data)
            self.last_node = self.head
        else:
            self.last_node.next = Node(data)
            self.last_node = self.last_node.next
 
    def get_node(self, index):
        current = self.head
        for i in range(index):
            current = current.next
            if current is None:
                return None
        return current
 
 
def has_cycle(llist):
    slow = llist.head
    fast = llist.head
    while (fast != None and fast.next != None):
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False
 
 
a_llist = LinkedList()
 
data_list = input('Please enter the elements in the linked list: ').split()
for data in data_list:
    a_llist.append(int(data))
 
length = len(data_list)
if length != 0:
    values = '0-' + str(length - 1)
    last_ptr = input('Enter the index [' + values + '] of the node'
                     ' to which you want the last node to point'
                     ' (enter nothing to make it point to None): ').strip()
    if last_ptr == '':
        last_ptr = None
    else:
        last_ptr = a_llist.get_node(int(last_ptr))
        a_llist.last_node.next = last_ptr
 
if has_cycle(a_llist):
    print('The linked list has a cycle.')
else:
    print('The linked list does not have a cycle.')

1. An instance of LinkedList is created.
2. The user is prompted to enter the data items for the list.
3. The user is then prompted to select which node they would like the last node to point to or whether they would like it to point to None.
4. The function has_cycle is called with the linked list as argument to determine whether it has a cycle.
5. The result is then displayed.

Case 1:
Please enter the elements in the linked list: 1 2 3
Enter the index [0-2] of the node to which you want the last node to point (enter nothing to make it point to None): 0
The linked list has a cycle.
 
Case 2:
Please enter the elements in the linked list: 4 5
Enter the index [0-1] of the node to which you want the last node to point (enter nothing to make it point to None): 1
The linked list has a cycle.
 
Case 3:
Please enter the elements in the linked list: 9 1 4 5
Enter the index [0-3] of the node to which you want the last node to point (enter nothing to make it point to None): 
The linked list does not have a cycle.

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.