Insert node at middle of linked list

The given problem involves inserting a new node into the middle of a singly linked list. A linked list is a data structure where elements, called nodes, are connected sequentially. Each node contains data and a reference to the next node in the sequence. The objective is to insert a new node with a given value at the middle position of the linked list.

Problem Statement

Given a singly linked list, we need to insert a new node containing a given value at the middle position of the list. If the list has an odd number of nodes, the middle position will be exactly in the center. If the list has an even number of nodes, we consider the middle position to be slightly towards the end of the first half of the list.

Description with Example

Consider the following example to illustrate the problem:

Original Linked List: 1 → 2 → 3 → 4 → 5

We want to insert the value 6 at the middle position.

After Insertion: 1 → 2 → 3 → 6 → 4 → 5

Idea to Solve the Problem

To solve this problem, we can use a two-pointer approach. We'll maintain two pointers: one will move at twice the speed of the other. When the fast-moving pointer reaches the end of the list, the slow-moving pointer will be at the middle. Then, we can insert the new node after the slow-moving pointer.

Pseudocode

AddNodeAtMiddle(sll, data):
    Create a new node with 'data'
    If sll.head is NULL:
        Set sll.head to the new node
    Else:
        Initialize two pointers: 'slow' and 'fast' as sll.head
        While fast is not NULL and fast.next is not NULL:
            Move fast to fast.next.next
            Move slow to slow.next
        Set new node's next to slow.next
        Set slow.next to the new node

Algorithm Explanation

1. Create a new node with the given data.
2. If the linked list is empty (sll.head is NULL), set sll.head to the new node and return.
3. Initialize two pointers 'slow' and 'fast' to the head of the linked list.
4. Traverse the linked list with the following condition:
   • Move 'fast' two steps at a time (fast = fast.next.next).
   • Move 'slow' one step at a time (slow = slow.next).
5. When the 'fast' pointer reaches the end (fast is NULL or fast.next is NULL), the 'slow' pointer will be at the middle position.
6. Set the new node's next pointer to 'slow.next'.
7. Set 'slow.next' to the new node.
8. The new node has been inserted at the middle of the linked list.

1) Insert node at middle of linked list in c 2) Insert node at middle of linked list in java 3) Insert node at middle of linked list in c# 4) Insert node at middle of linked list in c++ 5) Insert node at middle of linked list in python 6) Insert node at middle of linked list in ruby 7) Insert node at middle of linked list in node js 8) Insert node at middle of linked list in kotlin 9) Insert node at middle of linked list in swift 10) Insert node at middle of linked list in scala 11) Insert node at middle of linked list in go 12) Insert node at middle of linked list in php 13) Adding node in middle of linked list in typescript 14) Add node in middle of linked list in vb.net

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. The algorithm traverses the entire list once to find the middle position and then performs constant-time operations to insert the new node. Therefore, the overall time complexity is linear in terms of the number of nodes in the linked list.