Skip to content

Latest commit

 

History

History
95 lines (67 loc) · 2.74 KB

237. Delete Node in a Linked List.md

File metadata and controls

95 lines (67 loc) · 2.74 KB

237. Delete Node in a Linked List

1. Description

Write a function to delete a node in a singly-linked list. You will not be given access to the head of the list, instead you will be given access to the node to be deleted directly.

It is guaranteed that the node to be deleted is not a tail node in the list.

Example 1:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

Example 2:

Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

Example 3:

Input: head = [1,2,3,4], node = 3
Output: [1,2,4]

Example 4:

Input: head = [0,1], node = 0
Output: [1]

Example 5:

Input: head = [-3,5,-99], node = -3
Output: [5,-99]

Constraints:

  • The number of the nodes in the given list is in the range [2, 1000];
  • -1000 <= Node.val <= 1000;
  • The value of each node in the list is unique;
  • The node to be deleted is in the list and is not a tail node.

2. Solutions

Solution 1: Language: C Replacement and free()

The usual way of deleting a node node from a linked list is to modify the next pointer of the node before it, to point to the node after it.

Since we do not have access to the node before the one we want to delete, we cannot modify the next pointer of that node in any way. Instead, we have to replace the value of the node we want to delete with the value in the node after it, and then delete the node after it.

Because we know that the node we want to delete is not the tail of the list, we can guarantee that this approach is possible.

For any pointer which would not use again, the free() command is required case by case. Check it every time.

  • Sunday, 18 October, 2020
  • Time Complexity: $O(1)$
  • Space Complexity: $O(1)$
  • Runtime: 4 ms, faster than 94.59% of C online submissions for Delete Node in a Linked List.
  • Memory Usage: 6.4 MB, less than 16.24% of C online submissions for Delete Node in a Linked List.
/*
Definition for singly-linked list.
struct ListNode {
    int val;
    struct ListNode *next;
};
*/

// Replace the next node with next->next one, and then free the required node.
void deleteNode(struct ListNode* node) {
    struct ListNode* delete_node = node->next;
    node->val = node->next->val;
    node->next = node->next->next;
    free(delete_node);
}