# Delete the kth element of a Linked List

Problem Statement: Given a linked list, delete the kth element of the linked list and print the updated linked list.

Note: K will always be between 1 and N, where N is the length of the LL.

Examples
```Example 1:
Input Format: 0->1->2, k=2
Result: 0->2

Explanation: The second element of the list is 1. After deleting it, the updated linked list will have 0 pointing to 2, which explains the result.
Example 2:
Input Format: 12->5->8->7, k=3
Result: 12->5->7
Explanation: Again, the third element of the list is 8. After removing the third node, the list has 5 pointing to 7, as shown in the result.
Example 3:
Input Format: 12->5->8->7, k=5
Result: 12->5->8->7
Explanation: In this case, k is greater than the length of the list (4), therefore no node will get deleted.
```

### Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

### Approach:

The most straightforward way to look at this problem is to delete the kth node and point the previous node [(k-1)th node] to the next node [(k+1)th node] to complete the linked list.

Edge cases to consider:

1. If the input linked list is empty, we return null, as there is nothing to delete.
2. If K equals 1 (meaning we need to delete the first node), we follow the same steps we followed while deleting the head of the list.
3. If K equals the length of the linked list, we need to delete the tail of the linked list.
4. If the linked list has a single element, K can only take value 1 hence we delete this node and return null.

### Algorithm:

• To start the problem, initialize a pointer temp to the head of the list and a pointer prev to NULL. The temp pointer will be used to traverse the list till the kth node, and the prev pointer will keep track of the previous node that the temp pointer is pointing to.
• Initialize one more variable cnt, which will be used to keep track of the number of nodes traversed. Once cnt equals k, this means we have reached the kth node. If we have completed the traversal, then in this case, we have k greater than the length of the list, therefore no node will get deleted.
• If cnt equals k, then the temp pointer is pointing to the kth node. Delete this node and point the previous node [(k-1)th] to the next node [(k+1)th] to get the linked list.
Note: In the case of languages like Java, Python, and Javascript, there is no need for the deletion of objects or nodes because these have an automatic garbage collection mechanism that automatically identifies and reclaims memory that is no longer in use.

Thus, the updated Linked List looks like this:

Code:

## C++ Code

``````// Definition of a Node in a linked list
class Node {
public:
int data;
Node* next;

// Constructor with both data and next pointer
Node(int data1, Node* next1) {
data = data1;
next = next1;
}

// Constructor with only data, sets next to nullptr
Node(int data1) {
data = data1;
next = nullptr;
}
};

// Function to print the linked list
cout << head->data << " ";
}
}

// Function to delete the k-th node in a linked list
Node* deleteK(Node* head, int k) {
// Check if the list is empty

// If k is 1, delete the first node
if (k == 1) {
delete (temp);
}

// Traverse the list to find the k-th node
Node* prev = NULL;
int cnt = 0;

while (temp != NULL) {
cnt++;
// If the k-th node is found
if (cnt == k) {
// Adjust the pointers to skip the k-th node
prev->next = prev->next->next;
// Delete the k-th node
delete temp;
break;
}
// Move to the next node
prev = temp;
temp = temp->next;
}

}

int main() {
// Create a linked list from a vector
vector<int> arr = {0, 1, 2};
int k = 2;
// Delete the k-th node in the linked list

// Print the modified linked list

return 0;
}
``````

Output: 0 2

Time Complexity: O(N) worst case, when deleting the tail and O(1) best case, when deleting the head.

Space Complexity: O(1), as we have not used any extra space.

## Java Code

``````class Node {
public int data;
public Node next;

// Constructor with both data and next pointer
public Node(int data, Node next) {
this.data = data;
this.next = next;
}

// Constructor with only data, sets next to null
public Node(int data) {
this.data = data;
this.next = null;
}
}

// Function to print the linked list
}
}

// Function to delete the k-th node in a linked list
static Node deleteK(Node head, int k) {
// Check if the list is empty

// If k is 1, delete the first node
if (k == 1) {
temp = null;
}

// Traverse the list to find the k-th node
Node prev = null;
int cnt = 0;

while (temp != null) {
cnt++;
// If the k-th node is found
if (cnt == k) {
// Adjust the pointers to skip the k-th node
prev.next = prev.next.next;
// Delete the k-th node
temp = null;
break;
}
// Move to the next node
prev = temp;
temp = temp.next;
}

}

public static void main(String[] args) {
int[] arr = {0, 1, 2};
int k = 2;
// Delete the k-th node in the linked list

// Print the modified linked list
}
}
``````

Output: 0 2

Time Complexity: O(N) worst case, when deleting the tail and O(1) best case, when deleting the head.

Space Complexity: O(1), as we have not used any extra space.

## Python Code

``````class Node:
def __init__(self, data, next_node=None):
self.data = data
self.next = next_node

# Function to print the linked list
print()

# Function to delete the k-th node in a linked list
# Check if the list is empty

# If k is 1, delete the first node
if k == 1:
temp = None

# Traverse the list to find the k-th node
prev = None
cnt = 0

while temp is not None:
cnt += 1
# If the k-th node is found
if cnt == k:
# Adjust the pointers to skip the k-th node
prev.next = prev.next.next
# Delete the k-th node
temp = None
break
# Move to the next node
prev = temp
temp = temp.next

arr = [0, 1, 2]
k = 2

# Delete the k-th node in the linked list

# Print the modified linked list
``````

Output: 0 2

Time Complexity: O(N) worst case, when deleting the tail and O(1) best case, when deleting the head.

Space Complexity: O(1), as we have not used any extra space.

## JavaScript Code

``````class Node {
constructor(data, next) {
this.data = data;
this.next = next;
}
}

// Function to print the linked list
}
}

// Function to delete the k-th node in a linked list
// Check if the list is empty

// If k is 1, delete the first node
if (k === 1) {
temp = null;
}

// Traverse the list to find the k-th node
let prev = null;
let cnt = 0;

while (temp !== null) {
cnt++;
// If the k-th node is found
if (cnt === k) {
// Adjust the pointers to skip the k-th node
prev.next = prev.next.next;
// Delete the k-th node
temp = null;
break;
}
// Move to the next node
prev = temp;
temp = temp.next;
}

}

let arr = [0, 1, 2];
let k = 2;

// Delete the k-th node in the linked list

// Print the modified linked list