Detect if a Linked List is Circular in DSA Python - Build from Scratch

Detect if a Linked List is Circular

📖 Scenario: Imagine you have a chain of connected train cars. Sometimes, the last car connects back to an earlier car, making a loop. We want to check if the train cars form such a loop or if the chain ends normally.

🎯 Goal: You will build a simple linked list and write code to check if it forms a circular loop or not.

📋 What You'll Learn

Create a linked list with exactly 4 nodes with values 10, 20, 30, and 40

Add a variable called head pointing to the first node

Write a function called is_circular that takes head and returns True if the list is circular, else False

Test the function on a circular linked list where the last node points back to the second node

Print the result of the circular check

💡 Why This Matters

🌍 Real World

Circular linked lists are used in real-world applications like music playlists that repeat, or in operating systems for task scheduling where the tasks cycle continuously.

💼 Career

Understanding how to detect cycles in linked lists is important for software developers working with data structures, debugging memory leaks, or designing efficient algorithms.

1

Create the linked list nodes and connect them

Create a class called Node with attributes data and next. Then create 4 nodes with values 10, 20, 30, and 40. Connect them in order so that each node's next points to the next node. Finally, create a variable called head that points to the first node.

DSA Python

# Define Node class and create 4 connected nodes
# Your code here

Hint

Remember, each node should have a data value and a next pointer. Connect nodes by setting node1.next = node2, and so on.

2

Make the linked list circular by connecting last node to second node

Modify the linked list so that the last node (node4) points back to the second node (node2), creating a loop.

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

node1 = Node(10)
node2 = Node(20)
node3 = Node(30)
node4 = Node(40)

node1.next = node2
node2.next = node3
node3.next = node4

head = node1

# Make the list circular by connecting node4.next to node2
# Your code here

Hint

Set node4.next = node2 to create the circular link.

3

Write a function to detect if the linked list is circular

Write a function called is_circular that takes the head of the linked list as input. Use two pointers called slow and fast. Move slow by one step and fast by two steps in a loop. If fast or fast.next becomes None, return False. If slow and fast meet, return True.

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

node1 = Node(10)
node2 = Node(20)
node3 = Node(30)
node4 = Node(40)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2

head = node1

def is_circular(head):
    # Your code here

Hint

Use the 'slow and fast pointer' method to detect loops. Move slow by one and fast by two steps. If they meet, the list is circular.

4

Print the result of the circular linked list check

Call the function is_circular with head and print the result.

DSA Python

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

node1 = Node(10)
node2 = Node(20)
node3 = Node(30)
node4 = Node(40)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2

head = node1

def is_circular(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

# Print the result of is_circular(head)
# Your code here

Hint

Use print(is_circular(head)) to show if the list is circular.