Problem Statement: Given a linked list, an integer K, and a value val, your task is to insert a new node with the given value val before the Kth node in the list.
Examples
Example 1:
Input Format: 0->1->2 , val = 5, k=2
Result: 0->5->1->2
Explanation: We need to insert the value 5 at the 2nd position in the given Linked List.
Example 2:
Input Format:12->5->8->7, val = 100, k=3
Result: 12->5->100->8->7
Explanation: Again, we need to insert the value 100 at the 3rd position in the Linked List.
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Approach:
The intuition is to first traverse till the position of insertion, let’s say we have to insert at the 3rd position, then we will traverse up to the 2nd position and then insert the node after this position.
To insert the node, we simply create a new node with the given value val, and then make sure the node is placed after the 2nd position by changing the links.
There are a few edge cases to consider:
If k equals 1, then this is the same as inserting at the head of the linked list. You may refer to this article for more understanding.
If k equals the length of the linked list + 1, then this is the same as inserting after the tail of the linked list. You may refer to this article for more understanding.
Algorithm:
Initialize a temp pointer that will be used to traverse the list. Also, create a cnt variable that will store the number of nodes traversed. Traverse till the (k-1)th node.
Having reached the (k-1)th node, create the new node with the given value.
Now, there are two steps to be done for the insertion of the newly created node:
First, point the newly created node to the (k)th node (temp->next)
Then point (k-1)th node to the newly created node to complete the insertion
If the traversal is completed, this means that k was larger than the length of the linked list +1, and hence no node will get inserted.
Code:
C++ Code
// Node class to represent a linked list node
class Node {
public:
int data;
Node* next;
// Constructor with both data and next node
Node(int data1, Node* next1) {
data = data1;
next = next1;
}
// Constructor with only data (assuming next is initially null)
Node(int data1) {
data = data1;
next = nullptr;
}
};
// Function to print the linked list
void printLL(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
// Function to insert a new node at position k in the linked list
Node* insertAtK(Node* head, int val, int k) {
// If the linked list is empty and k is 1, insert the new node as the head
if (head == NULL) {
if (k == 1)
return new Node(val);
else
return head;
}
// If k is 1, insert the new node at the beginning of the linked list
if (k == 1)
return new Node(val, head);
int cnt = 0;
Node* temp = head;
// Traverse the linked list to find the node at position k-1
while (temp != NULL) {
cnt++;
if (cnt == k - 1) {
// Insert the new node after the node at position k-1
Node* newNode = new Node(val, temp->next);
temp->next = newNode;
break;
}
temp = temp->next;
}
return head;
}
int main() {
// Sample array, value, and position for insertion
vector<int> arr = {12, 8, 5, 7};
int val = 100;
int k = 3;
// Creating a linked list with initial elements from the array
Node* head = new Node(arr[0]);
head->next = new Node(arr[1]);
head->next->next = new Node(arr[2]);
head->next->next->next = new Node(arr[3]);
// Inserting a new node at position k in the linked list
head = insertAtK(head, val, k);
// Printing the linked list
printLL(head);
return 0;
}
Output:
12 8 100 5 7
Time Complexity: O(N) worst case, when insertion happens at the tail and O(1) best case, when insertion happens at the head.
Space Complexity: O(1), as we have not used any extra space.
Java Code
// Node class to represent a linked list node
class Node {
public int data;
public Node next;
// Constructor with both data and next node
public Node(int data1, Node next1) {
data = data1;
next = next1;
}
// Constructor with only data (assuming next is initially null)
public Node(int data1) {
data = data1;
next = null;
}
}
public class Main {
// Function to print the linked list
public static void printLL(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
}
// Function to insert a new node at position k in the linked list
public static Node insertAtK(Node head, int val, int k) {
// If the linked list is empty and k is 1, insert the new node as the head
if (head == null) {
if (k == 1)
return new Node(val);
else
return head;
}
// If k is 1, insert the new node at the beginning of the linked list
if (k == 1)
return new Node(val, head);
int cnt = 0;
Node temp = head;
// Traverse the linked list to find the node at position k-1
while (temp != null) {
cnt++;
if (cnt == k - 1) {
// Insert the new node after the node at position k-1
Node newNode = new Node(val, temp.next);
temp.next = newNode;
break;
}
temp = temp.next;
}
return head;
}
public static void main(String[] args) {
// Sample array, value, and position for insertion
List<Integer> arr = Arrays.asList(12, 8, 5, 7);
int val = 100;
int k = 3;
// Creating a linked list with initial elements from the array
Node head = new Node(arr.get(0));
head.next = new Node(arr.get(1));
head.next.next = new Node(arr.get(2));
head.next.next.next = new Node(arr.get(3));
// Inserting a new node at position k in the linked list
head = insertAtK(head, val, k);
// Printing the linked list
printLL(head);
}
}
Output:
12 8 100 5 7
Time Complexity: O(N) worst case, when insertion happens at the tail and O(1) best case, when insertion happens at the head.
Space Complexity: O(1), as we have not used any extra space.
Python Code
# Node class to represent a linked list node
class Node:
def __init__(self, data1, next1=None):
self.data = data1
self.next = next1
# Function to print the linked list
def printLL(head):
while head is not None:
print(head.data, end=" ")
head = head.next
# Function to insert a new node at position k in the linked list
def insertAtK(head, val, k):
# If the linked list is empty and k is 1, insert the new node as the head
if head is None:
if k == 1:
return Node(val)
else:
return head
# If k is 1, insert the new node at the beginning of the linked list
if k == 1:
return Node(val, head)
cnt = 0
temp = head
# Traverse the linked list to find the node at position k-1
while temp is not None:
cnt += 1
if cnt == k - 1:
# Insert the new node after the node at position k-1
new_node = Node(val, temp.next)
temp.next = new_node
break
temp = temp.next
return head
if __name__ == "__main__":
# Sample array, value, and position for insertion
arr = [12, 8, 5, 7]
val = 100
k = 3
# Creating a linked list with initial elements from the array
head = Node(arr[0])
head.next = Node(arr[1])
head.next.next = Node(arr[2])
head.next.next.next = Node(arr[3])
# Inserting a new node at position k in the linked list
head = insertAtK(head, val, k)
# Printing the linked list
printLL(head)
Output:
12 8 100 5 7
Time Complexity: O(N) worst case, when insertion happens at the tail and O(1) best case, when insertion happens at the head.
Space Complexity: O(1), as we have not used any extra space.
JavaScript Code
// Node class to represent a linked list node
class Node {
constructor(data1, next1 = null) {
this.data = data1;
this.next = next1;
}
}
// Function to print the linked list
function printLL(head) {
while (head !== null) {
console.log(head.data + " ");
head = head.next;
}
}
// Function to insert a new node at position k in the linked list
function insertAtK(head, val, k) {
// If the linked list is empty and k is 1, insert the new node as the head
if (head === null) {
if (k === 1) {
return new Node(val);
} else {
return head;
}
}
// If k is 1, insert the new node at the beginning of the linked list
if (k === 1) {
return new Node(val, head);
}
let cnt = 0;
let temp = head;
// Traverse the linked list to find the node at position k-1
while (temp !== null) {
cnt++;
if (cnt === k - 1) {
// Insert the new node after the node at position k-1
const new_node = new Node(val, temp.next);
temp.next = new_node;
break;
}
temp = temp.next;
}
return head;
}
// Sample array, value, and position for insertion
const arr = [12, 8, 5, 7];
const val = 100;
const k = 3;
// Creating a linked list with initial elements from the array
let head = new Node(arr[0]);
head.next = new Node(arr[1]);
head.next.next = new Node(arr[2]);
head.next.next.next = new Node(arr[3]);
// Inserting a new node at position k in the linked list
head = insertAtK(head, val, k);
// Printing the linked list
printLL(head);
Output:
12 8 100 5 7
Time Complexity: O(N) worst case, when insertion happens at the tail and O(1) best case, when insertion happens at the head.
Space Complexity: O(1), as we have not used any extra space.
In case you are learning DSA, you should definitely check out our free A2Z DSA Course with videos and blogs.
Special thanks to Neerav Sethi for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article
