# 5 Effective Ways to Insert a New Node in the Middle of a Circular Linked List in Python

Rate this post

π‘ 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

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

# Example usage

# Print list function for demonstration
def print_list(node):
start = node
while True:
print(node.data, end=' ')
node = node.next
if node == start:
break

```

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

count = 1
current = current.next
count += 1
mid = (count // 2 if count % 2 == 0 else count // 2 + 1)
for _ in range(mid - 1):
current = current.next
new_node = Node(data)
new_node.next = current.next
current.next = new_node

# Example usage and print_list function assumed to be defined previously

```

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

if steps == 0:
new_node = Node(data)
new_node.next = current.next
current.next = new_node
current.next = head  # Maintain circularity
if inserted or current.next.next == head:
return (current, False)

count = 1
current = current.next
count += 1
mid = (count // 2 if count % 2 == 0 else count // 2 + 1)

# Example usage and print_list function assumed to be defined previously

```

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

return Node(data)
count = 1  # Initialize counter
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

# Example usage and print_list function assumed to be defined previously

```

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

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

# Example usage and print_list function assumed to be defined previously

`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.