# 10 Circular Linked List Interview Questions and Answers

Prepare for your next technical interview with this guide on circular linked lists, covering their structure, applications, and implementation techniques.

Prepare for your next technical interview with this guide on circular linked lists, covering their structure, applications, and implementation techniques.

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.

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)

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)

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)

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

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

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

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)

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)

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)

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