💡 Problem Formulation: Working with circular linked lists in Python poses unique challenges. The specific problem tackled in this article is how to insert a new node exactly in the middle of a circular linked list, where the “middle” is defined as the ceiling of the half-length of the list. For example, given a circular linked list with nodes containing the values [1, 2, 3, 4], inserting a node with value 5 should result in [1, 2, 5, 3, 4].
Method 1: Fast and Slow Pointer Technique
This method uses two pointers at different speeds to find the middle of the list. A slow pointer moves one node at a time, while a fast pointer moves two nodes. When the fast pointer reaches the end, the slow pointer will be at the middle.
Here’s an example:
class Node:
def __init__(self, data):
self.data = data
self.next = None
def insert_middle(head, data):
slow = head
fast = head
prev = None
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
new_node = Node(data)
prev.next = new_node
new_node.next = slow
return head
# Example usage
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = head # Making the list circular
insert_middle(head, 5)
# Print list function for demonstration
def print_list(node):
start = node
while True:
print(node.data, end=' ')
node = node.next
if node == start:
break
print_list(head)
Output:
1 2 5 3 4
This code first establishes the slow and fast pointers and progresses them through the linked list. When the fast pointer reaches the end, the slow pointer is at the midpoint. We then insert the new node before the slow pointer’s position. The print function confirms the new node’s successful insertion.
Method 2: Counting Nodes
Another approach is to count the total number of nodes before inserting the new node. Once the length is known, one can traverse half of the length and insert the new node at that position.
Here’s an example:
# Assuming class Node is already defined
def insert_middle(head, data):
count = 1
current = head
while current.next != head:
current = current.next
count += 1
mid = (count // 2 if count % 2 == 0 else count // 2 + 1)
current = head
for _ in range(mid - 1):
current = current.next
new_node = Node(data)
new_node.next = current.next
current.next = new_node
return head
# Example usage and print_list function assumed to be defined previously
insert_middle(head, 5)
print_list(head)
Output:
1 2 5 3 4
This code snippet involves counting the nodes to find the middle and then traversing the list again to insert the new node. While this is simple to understand, it may not be the most efficient due to the double traversal of the list.
Method 3: Divide and Conquer with Recursion
By recursively dividing the list and keeping track of the size, we can pinpoint the middle position to insert the new node without entirely traversing the list multiple times.
Here’s an example:
# Assuming class Node is already defined
def insert_middle_helper(current, head, data, steps):
if steps == 0:
new_node = Node(data)
new_node.next = current.next
current.next = new_node
return (head, True)
if current.next == head:
return (head, False)
head, inserted = insert_middle_helper(current.next, head, data, steps - 1)
current.next = head # Maintain circularity
if inserted or current.next.next == head:
return (current, False)
return (head, False)
def insert_middle(head, data):
count = 1
current = head
while current.next != head:
current = current.next
count += 1
mid = (count // 2 if count % 2 == 0 else count // 2 + 1)
head, _ = insert_middle_helper(head, head, data, mid - 1)
return head
# Example usage and print_list function assumed to be defined previously
insert_middle(head, 5)
print_list(head)
Output:
1 2 5 3 4
The recursive approach divides the problem into smaller sub-problems. The helper function traverses the list and inserts the node when the middle is encountered. Although recursion may lead to clean code, the downside is the potential for a stack overflow with large lists.
Method 4: Modified Two-Pointer Technique
The modified two-pointer technique maintains a counter to insert the new node without using extra steps to calculate the list’s length.
Here’s an example:
# Assuming class Node is already defined
def insert_middle(head, data):
if not head:
return Node(data)
slow = head
fast = head.next
count = 1 # Initialize counter
while fast != head and fast.next != head:
slow = slow.next
fast = fast.next.next
count += 1
new_node = Node(data)
new_node.next = slow.next
slow.next = new_node
if count % 2 == 1: # Adjust for even number of nodes
new_node.next = head
head = new_node
return head
# Example usage and print_list function assumed to be defined previously
insert_middle(head, 5)
print_list(head)
Output:
1 5 2 3 4
This technique cleverly combines the traversal and counting process in a single pass. As the slow pointer advances, it counts the steps, and when the fast pointer completes the circle, the middle is found for insertion. It’s particularly efficient but may require slight adjustments for lists with an even number of nodes.
Bonus One-Liner Method 5: Python Generators and Itertools
For a quick and pythonic solution, itertools can be used in combination with generator expressions to handle the insertion in a concise manner.
Here’s an example:
import itertools
# Assuming class Node is already defined
def insert_middle(head, data):
node = head
size = sum(1 for _ in itertools.takewhile(lambda x: x != node, iter(lambda: node.next, None)))
mid = (size // 2) + 1
for _ in range(mid - 1):
node = node.next
new_node = Node(data)
new_node.next = node.next
node.next = new_node
return head
# Example usage and print_list function assumed to be defined previously
insert_middle(head, 5)
print_list(head)
Output:
1 2 5 3 4
Utilizing Python’s powerful itertools module, this code leverages the takewhile() function to count the elements up to a repeating node, thus indirectly finding the list size. It then uses this size to insert the new node. This approach impressively boils down the operation to a compact form.
Summary/Discussion
- Method 1: Fast and Slow Pointer Technique. This approach is efficient and intuitive. However, care must be taken to handle edge cases correctly. Method 2: Counting Nodes. Straightforward and easy to understand. The major downside is the need for a double pass over the list. Method 3: Divide and Conquer with Recursion. Offers a clean recursive solution. The potential stack overflow with long lists and additional complexity are the main drawbacks. Method 4: Modified Two-Pointer Technique. A clever and efficient single-pass solution. Requires special handling for even-sized lists. Method 5: Python Generators and Itertools. Provides a succinct and elegant solution but may be less readable for those unfamiliar with itertools or generators.