Log inSign up
mediumLeetCodeNot Started

Delete Node in a Linked List

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

There is a singly-linked list head and we want to delete a node node in it.

You are given the node to be deleted node. You will not be given access to the first node of head.

All the values of the linked list are unique, and it is guaranteed that the given node node is not the last node in the linked list.

Delete the given node. Note that by deleting the node, we do not mean removing it from memory. We mean: - The value of the given node should not exist in the linked list. - The number of nodes in the linked list should decrease by one. - All the values before node should be in the same order. - All the values after node should be in the same order.

Custom testing: - For the input, you should provide the entire linked list head and the value of the given node node. node should not be the last node of the list and should be an actual node in the list. - We will build the linked list and pass the node to your function. - The output will be the entire list after calling your function.

Example 1 · Delete Node 5:

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 · Delete Node 1:

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.

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.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the fundamental unidirectional constraint of singly linked lists.
  • Master the identity-swap technique: modifying node contents instead of pointer connections.
  • Recognize when problem constraints (not a tail node) are essential to algorithmic feasibility.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Deleting a node in a singly linked list without head access.
  • Guaranteed that the node to delete is not the tail node.
  • Need O(1) time and O(1) space node erasure.

Algorithmic Decision Tree:

  • When given node without prev: Overwrite node.val = node.next.val and skip node.next.
  • If the problem allowed deleting the tail node without head access, it would be mathematically impossible in a singly linked list.

Connected Patterns:

Remove Nth Node From End of ListRemove Linked List ElementsDelete Node in a BST

1. Brute Force — Shift All Values to Left

Intuition

Iterate from the target node to the end of the list. At each step, copy the next node's value to the current node. Finally, delete the tail node.

Algorithm

  1. Step 1: Set pointer curr = node.
  2. Step 2: While curr.next.next != null, set curr.val = curr.next.val and advance curr = curr.next.
  3. Step 3: At the second-to-last node, set curr.val = curr.next.val and disconnect curr.next = null.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode(int x) : val(x), next(NULL) {}
9};
10
11class Solution {
12public:
13 void deleteNode(ListNode* node) {
14 ListNode* curr = node;
15 while (curr->next->next != nullptr) {
16 curr->val = curr->next->val;
17 curr = curr->next;
18 }
19 curr->val = curr->next->val;
20 delete curr->next;
21 curr->next = nullptr;
22 }
23};
24
25int main() {
26 ListNode* head = new ListNode(4);
27 ListNode* node5 = new ListNode(5);
28 ListNode* node1 = new ListNode(1);
29 ListNode* node9 = new ListNode(9);
30 head->next = node5;
31 node5->next = node1;
32 node1->next = node9;
33
34 Solution sol;
35 sol.deleteNode(node5);
36
37 cout << "Brute Force Result: ";
38 ListNode* curr = head;
39 while (curr) {
40 cout << curr->val << (curr->next ? " -> " : "");
41 curr = curr->next;
42 }
43 cout << endl;
44 return 0;
45}

Time & Space Complexity

  • Time complexity: O(N) — Traverses and writes values for all K remaining nodes in the list.
  • Space complexity: O(1) — Modifies node values in place without allocating extra memory.

Why Brute Force Doesn't Scale:

Shifting all subsequent values takes O(K) time where K is the distance to the tail.

For a list of 1,000,000 nodes, shifting values takes ~3ms. O(1) value copying takes 0.0001ms.

2. Better — Vector/List Buffer Copy & Reassign

Intuition

Collect all values from node.next through the end of the list into an array/vector. Then iterate through the list starting at node, overwriting each node's value with the corresponding array value, and finally setting the second-to-last node's next pointer to null.

Algorithm

  1. Step 1: Traverse from node.next to the tail, recording each node's value into a dynamic array values.
  2. Step 2: Iterate pointer curr starting from node and for index i = 0 to values.length - 1, set curr.val = values[i].
  3. Step 3: At the penultimate position, set curr.next = null to discard the redundant tail node.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6struct ListNode {
7 int val;
8 ListNode *next;
9 ListNode(int x) : val(x), next(NULL) {}
10};
11
12class Solution {
13public:
14 void deleteNode(ListNode* node) {
15 vector<int> vals;
16 ListNode* curr = node->next;
17 while (curr != nullptr) {
18 vals.push_back(curr->val);
19 curr = curr->next;
20 }
21 curr = node;
22 for (int i = 0; i < vals.size(); ++i) {
23 curr->val = vals[i];
24 if (i == (int)vals.size() - 1) {
25 delete curr->next;
26 curr->next = nullptr;
27 } else {
28 curr = curr->next;
29 }
30 }
31 }
32};
33
34int main() {
35 ListNode* head = new ListNode(4);
36 ListNode* node5 = new ListNode(5);
37 ListNode* node1 = new ListNode(1);
38 ListNode* node9 = new ListNode(9);
39 head->next = node5;
40 node5->next = node1;
41 node1->next = node9;
42
43 Solution sol;
44 sol.deleteNode(node5);
45
46 cout << "Better C++ Result: ";
47 ListNode* curr = head;
48 while (curr) {
49 cout << curr->val << (curr->next ? " -> " : "");
50 curr = curr->next;
51 }
52 cout << endl;
53 return 0;
54}

Time & Space Complexity

  • Time complexity: O(N) — Traverses all remaining nodes from node.next to collect values into an auxiliary buffer of length K, then re-assigns values and cuts the tail.
  • Space complexity: O(N) — Allocates an auxiliary array/vector of size O(N) to store successor values.

3. Optimal — Copy Next Value & Bypass (O(1) Constant Time)

Intuition

Copy the value of the next node into the current node: node.val = node.next.val. Then skip the next node by pointing node.next = node.next.next. The current node effectively masquerades as its successor, while the duplicate successor node is excised.

Algorithm

  1. Step 1: Overwrite node.val = node.next.val.
  2. Step 2: In C++, save pointer to next node temp = node.next to prevent memory leak.
  3. Step 3: Point node.next = node.next.next.
  4. Step 4: In C++, call delete temp.

Delete Node Master Trace

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Target node now contains 1
Visual state
Values and pointers at this exact step
linked list
node → 1
Node 1
4
Node 2
1
Node 3
1
Node 4
9
NULL
Check / comparison
node.val updated from 5 to 1
Decision / next transition
Value copied
Why this step matters

Target node now contains 1.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode(int x) : val(x), next(NULL) {}
9};
10
11class Solution {
12public:
13 void deleteNode(ListNode* node) {
14 ListNode* nextNode = node->next;
15 node->val = nextNode->val;
16 node->next = nextNode->next;
17 delete nextNode; // Free memory in C++
18 }
19};
20
21int main() {
22 ListNode* head = new ListNode(4);
23 ListNode* node5 = new ListNode(5);
24 ListNode* node1 = new ListNode(1);
25 ListNode* node9 = new ListNode(9);
26 head->next = node5;
27 node5->next = node1;
28 node1->next = node9;
29
30 Solution sol;
31 sol.deleteNode(node5);
32
33 cout << "Optimal C++ Output: ";
34 ListNode* curr = head;
35 while (curr) {
36 cout << curr->val << (curr->next ? " -> " : "");
37 curr = curr->next;
38 }
39 cout << endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(1) — Performs exactly 2 pointer/value assignments in constant time.
  • Space complexity: O(1) — Uses zero additional memory.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Shift All Downstream ValuesO(N)O(1)Shift every node value from node to tail one position to the left, then delete the final node.Iterating through the entire rest of the list.
2.Optimal — Copy Next Value & Bypass (O(1))OptimalO(1)O(1)Copy node.next.val directly into node.val, then set node.next = node.next.next.Optimal.

Common Pitfalls & Crucial Edge Cases

Attempting to Delete the Tail Node

If node.next == null, node.next.val throws a NullPointerException. This is why the problem explicitly guarantees node is not the tail.

Memory Leak in C++

Failing to free node->next before reassigning pointers in manual memory management environments.

Thinking You Need Head Access

Trying to traverse backwards or searching for head when value overwriting works in O(1).

Crucial Edge Cases to Validate:

  • Node is Second Node — [4, 5, 1, 9], node = 5 -> [4, 1, 9].
  • Node is Penultimate Node — [4, 5, 1, 9], node = 1 -> [4, 5, 9].
  • 2-Node List Deleting First Node — [1, 2], node = 1 -> [2].

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the trick immediately: 'Since we don't have the previous pointer, we copy the successor's data and bypass the successor.'
  2. Highlight the edge case to the interviewer: 'This trick only works because the problem guarantees the node is not the tail. If it were the tail, deletion without head access would be impossible in a singly linked list.'
  3. In C++, explicitly mention freeing memory (delete temp) to demonstrate production readiness.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is it impossible to delete the tail node of a singly linked list with only a reference to that tail node?

2.What is the time complexity of the optimal value copy and bypass approach?

3.What happens to the node after node.next in memory in languages like Java and Python?

Back to DSA Sheet