How to Delete Node in a Linked List (Given Only Access to That Node)?

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is

1 -> 2 -> 3 -> 4

and you are given the third node with value 3, the linked list should become:

1 -> 2 -> 4

after calling your function.

O(1) solution

One advantage of Linked List (using pointers) is that it is constant time to insert and delete a node from the list. However, the search has an average O(n) linear complexity. If the root node is given, you can search the node from the root using O(n) linear search to find the previous node of the to-be-deleted node.

However, this is not necessary, we can just re-arrange the pointers. Let’s take a closer look.

Node A -> B -> C -> D. If we want to delete node B..

1. Make B = C, so the list becomes A -> C -> D and C’ -> D. C’ is the original C node and after this, there isn’t any node linking to it.
2. Navigate to the C’ node and delete it.

The full C++ solution is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        if (node != NULL) {
            auto nextNode = node->next;
            node->val = nextNode->val;
            node->next = nextNode->next;
            node = nextNode;
            delete node;
        }
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        if (node != NULL) {
            auto nextNode = node->next;
            node->val = nextNode->val;
            node->next = nextNode->next;
            node = nextNode;
            delete node;
        }
    }
};

singly-linked-list

Please note that we can’t delete the tail node without other knowledge and that is why it says (except the tail) in the description.

Linked List is not used when:

1. Need constant search time
2. Need constant random access
3. Space is limited (Nodes in the list require an extra space (saving the next pointer)

When the Linked List is preferred:

1. Need constant insert and deletion complexity
2. Does not need to pre-allocate space, easy to grow/shrink the list at runtime

The general approach to delete nodes (with target) from a linked list: Recursive Algorithm to Delete a Node from a Singly Linked List

–EOF (The Ultimate Computing & Technology Blog) —