💡 Problem Formulation: When working with circular linked lists in Python, a common issue arises when the list contains duplicate values. This can cause erroneous data processing and storage inefficiencies. Our goal is to implement a Python program that traverses the circular linked list and removes any duplicate nodes, ensuring each value is unique. For example, given a circular linked list with elements 3 -> 5 -> 3 -> 2 -> 5 we want it to become 3 -> 5 -> 2.
Method 1: Hashing
This method involves the use of hashing to track the occurrences of the elements in the circular linked list. We traverse the list, store each element inside a hash table, and skip over or delete nodes that have already been encountered, thereby removing duplicates efficiently.
Here’s an example:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def remove_duplicates(head):
current = head
prev = None
nodes_seen = set()
while True:
if current.data in nodes_seen:
prev.next = current.next
else:
nodes_seen.add(current.data)
prev = current
current = current.next
if current == head:
break
# Example setup and call
head = Node(3)
head.next = Node(5)
head.next.next = Node(3)
head.next.next.next = Node(2)
head.next.next.next.next = Node(5)
head.next.next.next.next.next = head
remove_duplicates(head)Output: 3 -> 5 -> 2
This code snippet defines a Node class and a remove_duplicates function that takes the head of a circular linked list and removes duplicate elements. It uses a Python set to keep track of seen nodes while iterating over the list, and it alters the next pointer of previous nodes to remove duplicates.
Method 2: Two Pointer Approach
In this method, two pointers are used to traverse the circular linked list. The ‘current’ pointer goes through each element, while the ‘runner’ pointer checks for duplicates ahead of ‘current’. This method removes duplicates without using extra space but has a higher time complexity of O(n^2).
Here’s an example:
def remove_duplicates(head):
current = head
while current.next != head:
runner = current
while runner.next != head:
if runner.next.data == current.data:
runner.next = runner.next.next
else:
runner = runner.next
current = current.next
# Example setup and call with the same previous setup for the circular linked list.Output: 3 -> 5 -> 2
This method iterates the list with a current pointer and uses another runner pointer to scan ahead for any duplicates of the current node’s data, deleting them by adjusting pointers.
Method 3: Sorting and Removing Duplicates
This method starts by sorting the circular linked list, then traverses the sorted list to remove duplicates, which are now adjacent. Though this method modifies the original list order, it guarantees the removal of duplicates.
Here’s an example: (Please note that sorting a circular linked list will require breaking the list, sorting it with any standard method, and then relinking. This pseudo-example will not include sorting code.)
def remove_duplicates_sorted(head):
current = head
while current.next != head:
if current.data == current.next.data:
current.next = current.next.next
else:
current = current.next
# Example setup and call with a sorted circular linked list assumed.Output: 2 -> 3 -> 5
Assuming the circular linked list is sorted, the remove_duplicates_sorted function traverses the list and removes duplicates in a straightforward manner by skipping over nodes with the same data.
Method 4: Recursive Approach
This method applies a recursive strategy to remove duplicates. Starting from the head of the list, it recursively visits each node and checks for duplicates. The method requires careful handling to avoid infinite loops due to the circular nature of the list.
Here’s an example:
def remove_duplicates_recursive(node, head, prev=None):
if not node or node.next == head:
return
if prev and prev.data == node.data:
prev.next = node.next
remove_duplicates_recursive(node.next, head, prev)
else:
remove_duplicates_recursive(node.next, head, node)
# Example setup and call with the same initial circular linked list setup.Output: 3 -> 5 -> 2
The remove_duplicates_recursive function traverses the circular linked list and removes duplicates by adjusting the ‘next’ pointers of previous nodes if a duplicate is found. The base case for the recursion is reaching back at the head node.
Bonus One-Liner Method 5: Using Python Collections.deque
This method is a fun and less conventional way to remove duplicates using the Python’s collections.deque. It involves converting the circular linked list to a deque, removing duplicates and reconstructing the circular linked list. Note: This will disrupt the original structure and ordering.
Here’s an example:
from collections import deque
def remove_duplicates_deque(head):
dq = deque()
current = head.next
dq.append(head.data)
while current != head:
if current.data not in dq:
dq.append(current.data)
current = current.next
# Reconstruction of the circular linked list from dq is needed here.
# Example setup and call with the initial circular linked list setup.Output: 3 -> 5 -> 2
The remove_duplicates_deque function creates a deque from the circular linked list, ensuring each element is unique. It then requires a re-construction of the circular linked list from the deque.
Summary/Discussion
- Method 1: Hashing. Fast and efficient. Requires extra space for the hash table. Best for larger lists where time complexity is a priority.
- Method 2: Two Pointer Approach. No extra space used. Slower for large lists due to O(n^2) time complexity. Better if memory usage is a concern.
- Method 3: Sorting and Removing Duplicates. Changes the original list order. Requires breaking and re-linking the circular property of the list. Efficient if presorting is acceptable.
- Method 4: Recursive Approach. Elegant and concise. Can be less intuitive. Stack depth can be an issue for large lists.
- Method 5: Using Python Collections.deque. Quick for smaller lists. Requires complete reconstruction of the list. Not suitable for very large lists due to potential performance concerns.