Delete Node In A Linked List - Leetcode Solution

Problem:

You are given a singly linked list and an integer k. You need to delete the k-th node from the given linked list.

Note:

• The given integer k will always be valid, meaning that the k-th node will always be present in the linked list and k will always be larger than 0.
• The head of the linked list is the first node, and it is 1-indexed.

Example:

Input: head = [1,2,3,4,5], k = 2 Output: [1,3,4,5] Explanation: We need to delete the node at position 2 (0-indexed) which is 2 in this case. After deleting node 2, the linked list becomes [1,3,4,5].

Solution:

To delete the k-th node from a singly linked list, we need to follow the below steps:

Step 1: Traverse the linked list till the node at (k-1)th position from the beginning. To traverse the linked list, we start at the head of the linked list and move to the next node until we reach the (k-1)th node.

Step 2: Once we reach the (k-1)th node, we need to set the next pointer of this node to point to the node next to the k-th node, i.e., node at (k+1)th position. This can be done by setting the next pointer of (k-1)th node to the next pointer of k-th node.

Step 3: Delete the k-th node by freeing the memory pointed by it.

The solution to this problem can be implemented as follows:

struct ListNode* deleteNode(struct ListNode* head, int k){ struct ListNode* temp, *prev; temp = head;

// If the first node is to be deleted
if(k==1){
    head = head->next;
    free(temp);
    return head;
}

// Traverse the linked list till (k-1)th node from the beginning
for(int i=1; i<k; i++){
    prev = temp;
    temp = temp->next;
}

prev->next = temp->next;  // Set the next pointer of (k-1)th node
free(temp);         // Free the memory pointed by the k-th node
return head;        // Return the updated head of the linked list

}

Time Complexity: The algorithm traverses the linked list once until the (k-1)th node is reached (in the worst case), so the time complexity is O(n), where n is the length of the linked list.

Space Complexity: The algorithm uses constant extra space, so the space complexity is O(1).

1