# Insert before the Kth element of the Linked List

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:

1. 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.
2. 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:
1.  First, point the newly created node to the (k)th node (temp->next)
2. 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
cout << head->data << " ";
}
}

// 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 (k == 1)
return new Node(val);
else
}

// If k is 1, insert the new node at the beginning of the linked list
if (k == 1)

int cnt = 0;

// 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;
}

}

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

// Inserting a new node at position k in the linked list

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) {
}
}

// 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 (k == 1)
return new Node(val);
else
}

// If k is 1, insert the new node at the beginning of the linked list
if (k == 1)

int cnt = 0;

// 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;
}

}

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

// Inserting a new node at position k in the linked list

}
}
``````

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

# Function to insert a new node at position k in the linked list
# If the linked list is empty and k is 1, insert the new node as the head
if k == 1:
return Node(val)
else:

# If k is 1, insert the new node at the beginning of the linked list
if k == 1:

cnt = 0

# 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

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

# Inserting a new node at position k in the linked list

``````

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 to insert a new node at position k in the linked list
// If the linked list is empty and k is 1, insert the new node as the head
if (k === 1) {
return new Node(val);
} else {
}
}

// If k is 1, insert the new node at the beginning of the linked list
if (k === 1) {
}

let cnt = 0;

// 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;
}

}

// 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

// Inserting a new node at position k in the linked list