Given a linked list and the node to be deleted, delete the node without accessing the head of the linked list

Intuition

This deletion is same as deleting a node from an array.

Approach

We use two pointers, pre and node to represent the previous and current node of the linked list, and we update the value of pre and node at each iteration. Finally, we delete the last node in the linked list.

Complexity

$$O(n)$$
$$O(1)$$

Code

 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) {
        ListNode* pre = nullptr;
        while (node->next) {
            node->val = node->next->val;
            pre = node;
            node = node->next;
        }
        pre->next = nullptr;
    }
};

References

Leetcode

237. Delete Node in a Linked List

Delete a node from a linked list with accessing the head of the linked list

Intuition

Approach

Complexity

Code

References