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:
If the input linked list is empty, we return null, as there is nothing to delete.
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.
If K equals the length of the linked list, we need to delete the tail of the linked list.
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
void printLL(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
// Function to delete the k-th node in a linked list
Node* deleteK(Node* head, int k) {
// Check if the list is empty
if (head == NULL)
return head;
// If k is 1, delete the first node
if (k == 1) {
Node* temp = head;
head = head->next;
delete (temp);
return head;
}
// Traverse the list to find the k-th node
Node* temp = head;
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;
}
return head;
}
int main() {
// Create a linked list from a vector
vector<int> arr = {0, 1, 2};
int k = 2;
Node* head = new Node(arr[0]);
head->next = new Node(arr[1]);
head->next->next = new Node(arr[2]);
// Delete the k-th node in the linked list
head = deleteK(head, k);
// Print the modified linked list
printLL(head);
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;
}
}
public class LinkedListExample {
// Function to print the linked list
static void printLL(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
}
// 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 (head == null)
return head;
// If k is 1, delete the first node
if (k == 1) {
Node temp = head;
head = head.next;
temp = null;
return head;
}
// Traverse the list to find the k-th node
Node temp = head;
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;
}
return head;
}
public static void main(String[] args) {
// Create a linked list
int[] arr = {0, 1, 2};
int k = 2;
Node head = new Node(arr[0]);
head.next = new Node(arr[1]);
head.next.next = new Node(arr[2]);
// Delete the k-th node in the linked list
head = deleteK(head, k);
// Print the modified linked list
printLL(head);
}
}
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
def printLL(head):
while head is not None:
print(head.data, end=" ")
head = head.next
print()
# Function to delete the k-th node in a linked list
def deleteK(head, k):
# Check if the list is empty
if head is None:
return head
# If k is 1, delete the first node
if k == 1:
temp = head
head = head.next
temp = None
return head
# Traverse the list to find the k-th node
temp = head
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
return head
# Create a linked list
arr = [0, 1, 2]
k = 2
head = Node(arr[0])
head.next = Node(arr[1])
head.next.next = Node(arr[2])
# Delete the k-th node in the linked list
head = deleteK(head, k)
# Print the modified linked list
printLL(head)
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 printLL(head) {
while (head !== null) {
console.log(head.data + " ");
head = head.next;
}
}
// Function to delete the k-th node in a linked list
function deleteK(head, k) {
// Check if the list is empty
if (head === null)
return head;
// If k is 1, delete the first node
if (k === 1) {
let temp = head;
head = head.next;
temp = null;
return head;
}
// Traverse the list to find the k-th node
let temp = head;
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;
}
return head;
}
// Create a linked list
let arr = [0, 1, 2];
let k = 2;
let head = new Node(arr[0]);
head.next = new Node(arr[1]);
head.next.next = new Node(arr[2]);
// Delete the k-th node in the linked list
head = deleteK(head, k);
// Print the modified linked list
printLL(head);
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.
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
