Delete a Node at a Given Position in a Linked List
Solve this Problemhead of a singly linked list and a 0-indexed position, delete the node at that index and return the head of the resulting list.
position = 0 is exactly the delete-at-the-beginning case. For any other position, the node being deleted is never visited directly — only the node right before it matters, since deleting means redirecting that node's next pointer straight past the target.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ number of nodes in head ≤ 10⁴ - ◆
-10⁹ ≤ node value ≤ 10⁹ - ◆
0 ≤ position < length of head — position is 0-indexed, so position 0 deletes the head
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | public Node deleteAtPosition(Node head, int position) { |
| 3 | if (position == 0) { |
| 4 | return head.next; |
| 5 | } |
| 6 | Node curr = head; |
| 7 | for (int i = 0; i < position - 1; i++) { |
| 8 | curr = curr.next; |
| 9 | } |
| 10 | curr.next = curr.next.next; |
| 11 | return head; |
| 12 | } |
| 13 | } |
| 14 |
2position is 2, not 0 — walk to the node just before the target index instead.
Approach & Solutions
Brute Force — Copy to Array Except That Index, Rebuild List
BruteWalk the entire list into a plain array, then remove the element at the given position, shifting everything after it one slot left. Throw the original list away and build a brand-new list from that array using a dummy + tail pointer. Correct, but every node — not just the one being deleted — is read and re-allocated.
O(n)O(n)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node deleteAtPosition(Node head, int position) {
9 List<Integer> vals = new ArrayList<>();
10 Node curr = head;
11 while (curr != null) {
12 vals.add(curr.val);
13 curr = curr.next;
14 }
15 vals.remove(position);
16 Node dummy = new Node(0);
17 Node tail = dummy;
18 for (int v : vals) {
19 tail.next = new Node(v);
20 tail = tail.next;
21 }
22 return dummy.next;
23 }
24}Optimal — Traverse to Position-1, Bypass the Target Node
OptimalPosition 0 is really just delete-at-the-beginning — handle it the same O(1) way. Otherwise, walk to the node just before the target position, then redirect its next pointer straight past the target node: curr.next = curr.next.next. The target node is never visited or modified — it's simply skipped over.
O(n)O(1) extra1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node deleteAtPosition(Node head, int position) {
9 if (position == 0) {
10 return head.next;
11 }
12 Node curr = head;
13 for (int i = 0; i < position - 1; i++) {
14 curr = curr.next;
15 }
16 curr.next = curr.next.next;
17 return head;
18 }
19}