Insert node into the middle of the linked list
Given a linked list containing n nodes. The problem is to insert a new node with data x at the middle of the list. If n is even, then insert the new node after the (n/2)th node, else insert the new node after the (n+1)/2th node.
Examples:
Input : list: 1->2->4->5 x = 3 Output : 1->2->3->4->5 Input : list: 5->10->4->32->16 x = 41 Output : 5->10->4->41->32->16Linked List | Set 2 (Inserting a node)
We have introduced Linked Lists in the previous post. We also created a simple linked list with 3 nodes and discussed linked list traversal.
All programs discussed in this post consider the following representations of linked list.
|
// A linked list node
class Node
{
public:
int data;
Node *next;
};
// This code is contributed by rathbhupendra
|
|
// A linked list node
struct Node
{
int data;
struct Node *next;
};
|
|
// Linked List Class
class LinkedList
{
Node head; // head of list
/* Node Class */
class Node
{
int data;
Node next;
// Constructor to create a new node
Node(int d) {data = d; next = null; }
}
}
|
|
# Node class
class Node:
# Function to initialize the node object
def __init__(self, data):
self.data = data # Assign data
self.next = None # Initialize next as null
# Linked List class
class LinkedList:
# Function to initialize the Linked List object
def __init__(self):
self.head = None
|
|
/* Linked list Node*/
public class Node
{
public int data;
public Node next;
public Node(int d) {data = d; next = null; }
}
|
|
<script>
// Linked List Class
var head; // head of list
/* Node Class */
class Node {
// Constructor to create a new node
constructor(d) {
this.data = d;
this.next = null;
}
}
// This code is contributed by todaysgaurav
</script>
|
In this post, methods to insert a new node in linked list are discussed. A node can be added in three ways
1) At the front of the linked list
2) After a given node.
3) At the end of the linked list.
Required knowledge
Basic C programming, Functions, Singly linked list, Dynamic memory allocation
Algorithm to insert node at the middle of singly Linked List
C Exercises: Insert a new node at the middle of the Linked List
Last update on December 20 2021 09:11:05 (UTC/GMT +8 hours)Middle of the Linked List
Difficulty: Easy
Understanding the Problem
Problem Description
Given a non-empty, singly linked list with head node head, write a program to return a middle node of the linked list. If there are even nodes, then there would be two middle nodes, we need to print the second middle element.
Example 1
Input: 11->2->13->44->5 Output: 13 Explanation: The middle element of the linked list is 13.Example 2
Input: 10->2->34->24->15->60 Output: 24 Explanation: As there are even number of nodes, return 24 as it is the second node among two middle elements.Solutions
- Two-Pass: Find the length of the linked list and return the (length/2)th node.
- One-Pass: Use two pointers, the 2nd pointer should traverse twice as fast at the first.
Before moving forward with the question, you must understand the properties of a linked list.
You can try this problem here.
1. Two-Pass
The question demands to find the middle of a singly linked list. We can simply find the total length of the linked list, in this way we can identify which node falls in the middle. To find the middle node, we can traverse again until we reach (length/2)th node.
Solution Steps
- Create a pointer p, pointing to the head.
- Iterate over the linked list until p reaches to the end of the linked list, thereby find the length of the list.
- Set p to head again. Now, increment p length/2 times. Now, the p is at the middle of the linked list node. Return the value at p
Pseudo Code
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
Critical Ideas To Think
- Why did we reinitialize p with the head?
- Which node will be returned if the length of the linked list is even?
- What if the linked list forms a loop?
2. One-Pass
Another way to solve this problem is to use a little trick. Instead of traversing twice, we can create two-pointers say slow_ptr and fast_ptr.We can make the fast_ptr twice as fast as slow_ptr. So, When the fast_ptr will reach to the end of the linked list, slow_ptr would still be at the middle, thereby pointing to the mid of the linked list.
Solutions Steps
- Create slow_ptr and fast_ptr pointing to the head initially.
- Increment fast_ptr by 2 and slow_ptr by 1 positions until fast_ptr and fast_ptr.next is not NULL
- Return the value at slow_ptr.
Pseudo Code
int middleNode(ListNode head) { ListNode slow = head ListNode fast = head while (fast != null and fast.next != null) { slow = slow.next fast = fast.next.next } return slow.data }Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
Critical Ideas To Think
- Why did we use two pointers?
- Why did we iterate until fast != null and fast.next != null ?
- Do both the discussed approaches affect the running time?
Comparison Of Different Approaches
Suggested Problems To Solve
- Remove Duplicates from Sorted List
- Merge Sort on Linked List
- Check if a singly linked list is a palindrome
- Detect and Remove Loop in a Linked List
- Sort a linked list using insertion sort
- Remove Nth Node from List End
Happy coding!
Enjoy Algorithms.