## Similar Problems

Similar Problems not available

# Delete Node In A Linked List - Leetcode Solution

LeetCode: Delete Node In A Linked List Leetcode Solution

Difficulty: Medium

Topics: linked-list

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).

## Delete Node In A Linked List Solution Code

`1`