10 Circular Linked List Interview Questions and Answers

Circular linked lists are a fundamental data structure in computer science, offering unique advantages over traditional linked lists. Unlike singly or doubly linked lists, circular linked lists have their last node pointing back to the first node, forming a continuous loop. This structure is particularly useful in applications requiring a circular traversal of elements, such as in round-robin scheduling or buffering data streams.

This article provides a curated selection of interview questions focused on circular linked lists, designed to help you understand their intricacies and applications. By working through these questions and answers, you’ll gain a deeper insight into how circular linked lists function and how to effectively implement and manipulate them in various scenarios.

Circular Linked List Interview Questions and Answers

1. What is a Circular Linked List and how does it differ from a singly linked list?

A Circular Linked List is a linked list where the last node points back to the first node, forming a circle. This differs from a Singly Linked List, where the last node points to null. Circular Linked Lists allow for continuous traversal, making them useful for applications like round-robin scheduling.

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

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.head.next = self.head
        else:
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            temp.next = new_node
            new_node.next = self.head

# Creating a Circular Linked List
cll = CircularLinkedList()
cll.append(1)
cll.append(2)
cll.append(3)

2. Write a function to insert a node at the beginning of a Circular Linked List.

Inserting a node at the beginning of a Circular Linked List involves updating the new node’s next pointer to point to the current head and updating the last node’s next pointer to point to the new node.

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

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def insert_at_beginning(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
        else:
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            new_node.next = self.head
            temp.next = new_node
            self.head = new_node

# Example usage:
cll = CircularLinkedList()
cll.insert_at_beginning(10)
cll.insert_at_beginning(20)

3. Write a function to insert a node at the end of a Circular Linked List.

To insert a node at the end of a Circular Linked List, adjust the pointers so the new node points to the head, and the previous last node points to the new node.

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

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def insert_at_end(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            new_node.next = self.head
        else:
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            temp.next = new_node
            new_node.next = self.head

# Example usage:
cll = CircularLinkedList()
cll.insert_at_end(1)
cll.insert_at_end(2)
cll.insert_at_end(3)

4. Write a function to traverse and print all elements in a Circular Linked List.

To traverse and print all elements in a Circular Linked List, start from any node and continue until you reach the starting node again.

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

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            self.head.next = self.head
        else:
            temp = self.head
            while temp.next != self.head:
                temp = temp.next
            temp.next = new_node
            new_node.next = self.head

    def traverse_and_print(self):
        if not self.head:
            return
        current = self.head
        while True:
            print(current.data, end=" ")
            current = current.next
            if current == self.head:
                break
        print()

# Example usage:
cll = CircularLinkedList()
cll.append(1)
cll.append(2)
cll.append(3)
cll.traverse_and_print()
# Output: 1 2 3

5. How would you detect if a given linked list has a loop? Provide a code example.

To detect if a linked list has a loop, use Floyd’s Cycle-Finding Algorithm. This involves two pointers: a slow pointer moving one step at a time, and a fast pointer moving two steps. If there’s a loop, the fast pointer will meet the slow pointer.

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def has_cycle(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True

    return False

# Example usage:
# Creating a linked list with a loop for demonstration
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2  # Creates a loop

print(has_cycle(node1))  # Output: True

6. Write a function to find the length of a Circular Linked List.

To find the length of a Circular Linked List, traverse the list while counting nodes until you encounter the starting node again.

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

def circular_linked_list_length(head):
    if not head:
        return 0

    current = head
    length = 1

    while current.next != head:
        length += 1
        current = current.next

    return length

# Example usage:
head = Node(1)
second = Node(2)
third = Node(3)

head.next = second
second.next = third
third.next = head

print(circular_linked_list_length(head))  # Output: 3

7. Write a function to split a Circular Linked List into two halves.

To split a Circular Linked List into two halves, find the midpoint and adjust the pointers to create two separate circular lists.

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

def split_circular_linked_list(head):
    slow_ptr = head
    fast_ptr = head

    while fast_ptr.next != head and fast_ptr.next.next != head:
        slow_ptr = slow_ptr.next
        fast_ptr = fast_ptr.next.next

    head1 = head
    head2 = slow_ptr.next
    slow_ptr.next = head1

    temp = head2
    while temp.next != head:
        temp = temp.next
    temp.next = head2

    return head1, head2

# Example usage:
# Creating a circular linked list with nodes 1 -> 2 -> 3 -> 4 -> 5 -> 1
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
head.next.next.next.next.next = head

head1, head2 = split_circular_linked_list(head)

8. Write a function to merge two Circular Linked Lists into one.

Merging two Circular Linked Lists involves connecting the end of the first list to the start of the second list and vice versa, maintaining the circular structure.

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

def merge_circular_linked_lists(head1, head2):
    if not head1 or not head2:
        return head1 if head1 else head2

    tail1 = head1
    while tail1.next != head1:
        tail1 = tail1.next

    tail2 = head2
    while tail2.next != head2:
        tail2 = tail2.next

    tail1.next = head2
    tail2.next = head1

    return head1

# Example usage:
# Assuming head1 and head2 are the heads of two circular linked lists
# merged_head = merge_circular_linked_lists(head1, head2)

9. Write a function to reverse a Circular Linked List.

Reversing a circular linked list involves changing the direction of the pointers so each node points to its previous node, and the last node points back to the new head.

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

def reverse_circular_linked_list(head):
    if not head or not head.next:
        return head

    prev = None
    current = head
    next_node = None

    while True:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
        if current == head:
            break

    head.next = prev
    head = prev

    return head

# Example usage:
# Creating a circular linked list: 1 -> 2 -> 3 -> 1
head = Node(1)
second = Node(2)
third = Node(3)
head.next = second
second.next = third
third.next = head

# Reversing the circular linked list
new_head = reverse_circular_linked_list(head)

10. Write a function to find the middle element of a Circular Linked List.

To find the middle element of a Circular Linked List, use the two-pointer technique, with one pointer moving at half the speed of the other.

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

def find_middle(head):
    if head is None:
        return None

    slow_ptr = head
    fast_ptr = head

    while fast_ptr.next != head and fast_ptr.next.next != head:
        slow_ptr = slow_ptr.next
        fast_ptr = fast_ptr.next.next

    return slow_ptr.data

# Example usage:
head = Node(1)
second = Node(2)
third = Node(3)
fourth = Node(4)
fifth = Node(5)

head.next = second
second.next = third
third.next = fourth
fourth.next = fifth
fifth.next = head

print(find_middle(head))  # Output: 3