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
- Create a new node with the given data.
- If the linked list is empty (sll.head is NULL), set sll.head to the new node and return.
- Initialize two pointers 'slow' and 'fast' to the head of the linked list.
- 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).
- When the 'fast' pointer reaches the end (fast is NULL or fast.next is NULL), the 'slow' pointer will be at the middle position.
- Set the new node's next pointer to 'slow.next'.
- Set 'slow.next' to the new node.
- 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.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment