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

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.