DSA sheet · Linked List · Basic operations pattern

Delete Node in Linked List

This video teaches how to remove the node at position x from a singly linked list, and it treats the three places a node can be: the head, somewhere in the middle, and the tail. The core move is one line, curr.next = curr.next.next, and the real lesson is where to stand when you run it (one node before the target) and which None checks keep it from crashing. The teacher solves it twice: iteratively with a loop, then recursively.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Linked list basics you need for this page
• Part A · Delete at position x, iterative
• Part B · Delete at position x, recursive
• Part C · Revision page

Part 0 · Before starting

What is a linked list node?

A linked list is a chain of nodes. Each node stores a value (val) and a link to the next node (next). The last node's next is None: the end of the chain.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val      # the number stored in this node
        self.next = next    # the next node, or None at the end

[1] → [2] → [3] → [4] → [5] → None
 ↑
head

• head points to the first node. It is the only door into the list. A node is "in the list" only if you can reach it by starting at head and following .next links.
• Walking: start a helper pointer (an alias, often called curr) at head and repeat curr = curr.next. We move the alias, not head, so we can still return the start of the list at the end.
• No index access. There is no list[i]. To reach position i you must walk from the head, one link at a time, so it costs O(i), up to O(n).
• Save what you still need before changing a pointer. Once you overwrite a node's next, the old next node can no longer be reached from that node. In deletion this is exactly what we want for the target node, but we must make sure the nodes after the target stay reachable. That's why we link the previous node to target.next in the same step.

What does "deleting" a node actually mean?

We never erase memory by hand in Python. We simply make sure no link points to that node any more. When nothing points to it, it is no longer part of the list (walking from head will never reach it), and Python's garbage collector frees it later. In C++ there's no garbage collector, so the teacher reminds C++ users to save the node in a temporary variable and delete it themselves.

Positions in this problem

Positions are counted from 1: the head is position 1, the next node is position 2, and so on. This matters for how many steps we walk.

Part A · Delete at position x, iterative

GFG · Delete in a Singly Linked List

1The question in simple words

You get the head of a singly linked list and a number x. Remove the node at position x (counting from 1) and return the head of the new list.

before: [8] → [2] → [3] → [1] → [7] → None
after:        [2] → [3] → [1] → [7] → None

before: [1] → [2] → [3] → [4] → [5] → None
after:  [1] → [2] → [4] → [5] → None

There are three situations: the node is the head, the node is in between, or the node is the last one. We'll check that one piece of code handles all three.

2What the constraints tell us

• The list can have up to 10⁵ nodes. 10⁵ × 10⁵ = 10¹⁰ is far above about 10⁸ operations, so anything quadratic would TLE. We need a linear solution, and one walk to the position is linear.
• x is a valid position (1 ≤ x ≤ length of the list). Still, we'll write the code so that it does not crash if x is too big.
• We'll also guard against an empty list (head is None): there is nothing to delete, so return None.

3Intuition: bypass the node

Picture the nodes as people holding hands in a line, each one holding only the hand of the person in front. To remove person 3, person 2 lets go of 3 and takes the hand of person 4 instead. Nobody holds person 3 any more, so 3 is out of the line, and the line is still unbroken.

In code, "person 2 takes person 4's hand" is: node2.next = node3.next. Since node3 is node2.next, this becomes curr.next = curr.next.next with curr standing on node 2.

4Building the logic from examples

Case 1: delete the head (x = 1). O(1), no walking

[1] → [2] → [3] → [4] → [5] → None
       ↑
   new head

Just return head.next (or move head = head.next and return head; both are the same). Why does this delete node 1? Because the list is only "what you can reach from the head". The new head is 2, and nothing points back to 1, so 1 is no longer part of the list. No loop, no walking: O(1).

Case 2: delete in the middle, e.g. x = 3

Right now, node 2 stores the address of node 3, and node 3 stores the address of node 4. To remove 3, the address that 3 was holding (node 4) must now be held by node 2.

before:  [1] → [2] → [3] → [4] → [5] → None
                ↑
               curr        curr.next = [3],  curr.next.next = [4]

after:   [1] → [2] ──────→ [4] → [5] → None
                     [3] ─┘   (nothing points to 3 any more)

The None checks: when would curr.next = curr.next.next crash?

• If curr is None, then curr.next means "next of nothing" → crash (Java calls it a NullPointerException; Python raises AttributeError).
• If curr.next is None (we're standing on the last node), then curr.next.next again asks for "next of nothing" → crash.

So we only delete if curr is not None and curr.next is not None.

Case 3: delete the tail, e.g. x = 5. Proving the code still works

[1] → [2] → [3] → [4] → [5] → None
                   ↑
                  curr     (x − 2 = 3 jumps: 1→2→3→4)

Is curr (node 4) None? No. Is curr.next (node 5) None? No. So we run 4.next = 5.next, and 5.next is None. Node 4 now points to None: node 5 is deleted, and 4 is the new tail. No special code for the tail was needed.

What if x is one past the end, e.g. x = 6?

x − 2 = 4 jumps: 1→2→3→4→5, so curr = node 5. Now curr.next is None, and without the check, curr.next.next would crash. With the check, we simply skip the deletion and return the list unchanged. This is the case the teacher uses to show why the second check is needed.

5Approach steps

1. If the list is empty, return None.
2. If x is 1, return head.next (the head is deleted).
3. Start curr at head and jump x − 2 times, so curr stands one node before the target.
4. If curr and curr.next both exist, skip the target: curr.next = curr.next.next.
5. Return head (unchanged, since the head wasn't deleted).

6Code (Python)

def deleteNode(head, x):
    if head is None:                 # empty list: nothing to delete
        return None
    if x == 1:                       # case 1: delete the head, O(1)
        return head.next

    curr = head
    for _ in range(x - 2):           # x-2 jumps: stand ONE BEFORE the target
        if curr is None:             # x is past the end (safety line)
            return head
        curr = curr.next

    if curr is not None and curr.next is not None:
        curr.next = curr.next.next   # bypass the target: this is the deletion
    return head

7Code line by line

8Dry run

List 1 → 2 → 3 → 4 → 5. Three runs: x = 3 (middle), x = 5 (tail), x = 6 (past the end).

Step-by-step for x = 3:

Snapshot just before the rewiring, and just after:

before:  [1] → [2] → [3] → [4] → [5] → None
          ↑     ↑
        head   curr

after:   [1] → [2]   [3] → [4] → [5] → None
                 │          ↑
                 └──────────┘
         (2 now points to 4; [3] still points to [4], but nobody points to [3])

9Complexity & remember

• Deleting the head: O(1) time, O(1) space. No travel at all.
• Deleting at position x: O(n) time in the worst case, because we must walk up to x − 2 links to get there (no index access). O(1) space: just one alias.

Part B · Delete at position x, recursive

1The question (same as Part A)

Same input (head, x), same output (head of the list with node x removed). The teacher shows the recursive version because recursion was covered earlier in the playlist, and turning a loop into recursion is good practice.

2What the constraints tell us

• Up to 10⁵ nodes. Recursion makes one call per node it passes, so it can go up to about 10⁵ calls deep. That is fine in Java/C++ on GFG, but note that Python's default recursion limit is about 1000. For a very long list in Python, the iterative version (Part A) is the safe choice.
• Same rule as before: x is a valid position.

3Intuition: each call asks "is it me?"

Each call stands on one node and holds a number x that means "the node to delete is x positions away, counting me as 1".

• If x is 1, the node to delete is this node. Give back what comes after it (head.next), which leaves this node out.
• Otherwise, the target is further ahead. Ask the next node to handle the rest, with x − 1 (it's one position closer now). Whatever list the next call gives back becomes my next. Then give back myself.

The things that change from one loop round to the next in Part A (where curr stands, how many jumps are left) become the parameters of the recursive call. That's the teacher's general rule for turning a loop into recursion.

4Building the logic from examples

Base cases (same as Part A)

• head is None → return None. (Empty list, or we walked past the end.)
• x == 1 → return head.next. This node is the one to remove.

Example: list 1 → 2 → 3 → 4 → 5, x = 2

1. First call: head = [1], x = 2. Not None, x isn't 1. The target is further on. Call again with head.next (node 2) and x − 1 = 1.
2. Second call: head = [2], x = 1. x is 1 → return head.next, which is node 3 (and with it 3 → 4 → 5).
3. Back in the first call: the returned node 3 must be stored as node 1's next: head.next = (result). Now 1 → 3 → 4 → 5. Node 2 is out.
4. The first call returns head (node 1), the full new list.

5Approach steps

1. If head is None → return None.
2. If x is 1 → return head.next.
3. Otherwise set head.next = deleteNode(head.next, x - 1).
4. Return head.

6Code (Python)

def deleteNode(head, x):
    if head is None:            # empty / walked past the end
        return None
    if x == 1:                  # this node is the target
        return head.next        # skip it
    head.next = deleteNode(head.next, x - 1)   # fix the rest, attach it to me
    return head

7Code line by line

8Dry run: x = 3 on 1 → 2 → 3 → 4 → 5

1. Call (1, x=3): not None, x ≠ 1 → calls (2, x=2). (1, 3) waits on the stack.
2. Call (2, x=2): x ≠ 1 → calls (3, x=1). (2, 2) waits.
3. Call (3, x=1): x == 1 → returns 3.next = node 4. This call leaves the stack.
4. Back in (2, x=2): 2.next = 4 → rewire: node 2 now points to 4. Returns node 2.
5. Back in (1, x=3): 1.next = 2 (it was already 2, so nothing really changes). Returns node 1.
6. Final list: 1 → 2 → 4 → 5.

The newest call is on top (red). Calls are pushed while walking forward, and on the way back each one re-attaches what it got to its own next.

And with x = 1, the very first call returns head.next at once: no recursion, nothing on the stack.

9Complexity & remember

• Deleting the head: O(1) time and O(1) space, because the first call returns straight away and makes no further calls.
• Deleting at position x: O(n) time, and O(n) space for the call stack (one waiting call per node passed).
• Which is better? The iterative version: same O(n) time but only O(1) space. The recursive one is for practice and understanding.

Part C · Revision page

class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next

def build(vals):
    head = None
    for v in reversed(vals):
        head = ListNode(v, head)
    return head

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

print(to_list(deleteNode(build([8, 2, 3, 1, 7]), 1)))   # [2, 3, 1, 7]
print(to_list(deleteNode(build([1, 2, 3, 4, 5]), 3)))   # [1, 2, 4, 5]
print(to_list(deleteNode(build([1, 2, 3, 4, 5]), 5)))   # [1, 2, 3, 4]
print(to_list(deleteNode(build([1, 2, 3, 4, 5]), 6)))   # [1, 2, 3, 4, 5]

Based on this video: Delete Node in Linked List | Iterative & Recursive