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

• Time complexity: iterate the linked list once. $$O(n)$$

• Space complexity: no extra space needed. $$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