Insert a Node in the Middle of a Singly Linked List

Inserting a Node in the Middle

Inserting a node in the middle of a singly linked list involves finding the appropriate position in the list and updating the next references of the surrounding nodes to include the new node. This operation requires traversing the list to find the desired insertion point.

---

Step-by-Step Process

Consider a singly linked list with the following structure before insertion:

Head -> 1 -> 2 -> 4 -> 5 -> None

We want to insert a new node with the value 3 between the nodes with values 2 and 4. Follow these steps:

1. Create a New Node: Create a new node with the desired value (3).
2. Initialize Two Pointers: Start with two pointers, slow and fast, both initialized to the head of the list.
3. Traverse the List: Move the slow pointer one step and the fast pointer two steps at a time until the fast pointer reaches the end of the list or the node before the last node.
4. Insert the New Node: Update the next reference of the new node to point to the node currently following the slow pointer, and update the slow pointer's next reference to point to the new node.

After performing these steps, the linked list will have the following structure:

Head -> 1 -> 2 -> 3 -> 4 -> 5 -> None

---

Python Program to Insert a Node in the Middle

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def insert_at_middle(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        slow = self.head
        fast = self.head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        new_node.next = slow.next
        slow.next = new_node

    def traverse(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Example usage:
linked_list = SinglyLinkedList()
linked_list.append(1)
linked_list.append(2)
linked_list.append(4)
linked_list.append(5)
print("Linked list before insertion:")
linked_list.traverse()  # Output: 1 -> 2 -> 4 -> 5 -> None
linked_list.insert_at_middle(3)
print("Linked list after insertion in the middle:")
linked_list.traverse()  # Output: 1 -> 2 -> 3 -> 4 -> 5 -> None

This Python program defines a singly linked list with methods for appending nodes, inserting a node in the middle, and traversing the list. The insert_at_middle method creates a new node, uses the slow and fast pointer technique to find the middle of the list, and updates the next references to include the new node.