☕ DSA Java Articles

Topics › Linked List › Learn 1D LinkedList

Deletion of the head of LL

Easy TUF ID 352 A2Z

Java source ↗ Edit this article ↗

Problem

You are given the head of a singly linked list. Remove the first node and return the head of the remaining list. If the list is empty there is nothing to remove, so return null; if it has one node, removing it leaves the empty list, which is also null.

Constraints: 0 ≤ n ≤ 10^5 nodes, values fit in a 32-bit signed integer. The operation must not visit the rest of the list.

Example 1

list = 1 -> 2 -> 3 -> 4 -> 5
answer = 2 -> 3 -> 4 -> 5      // the second node is the new head

Example 2

list = 42
answer = (empty)               // the only node is removed, the list is now null

Example 3

list = (empty)
answer = (empty)               // nothing to delete

The node type is the standard one with an int val and a ListNode next.

static class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Approach 1: Return the second node

Intuition. Because the list is identified only by a reference to its first node, deleting the head does not require touching the head node’s memory at all. If the caller starts treating the second node as the head, the first node is simply no longer part of the list. Java’s garbage collector reclaims it once nothing references it. So the entire operation is “read head.next and return it”, guarded against an empty list.

Algorithm.

  1. If head == null, return null: there is nothing to delete.
  2. Remember newHead = head.next.
  3. Set head.next = null so the removed node no longer points into the list.
  4. Return newHead.
static ListNode deleteHead(ListNode head) {
    if (head == null) return null;             // nothing to delete
    ListNode newHead = head.next;
    head.next = null;                          // detach the removed node so it no longer points into the list
    return newHead;
}

Complexity. Time O(1): a null check and two assignments. Space O(1).

Step 3 is not strictly required for correctness, and many solutions skip it. It is good hygiene for two reasons. If the caller still holds a reference to the old head (say, for logging), it cannot accidentally walk back into the live list through a stale next link. And in languages or environments where the old node is reused, a dangling pointer into the list is a classic source of bugs. In the test file, first.next == null after deleteHead(first) is asserted explicitly.

For a single-node list, head.next is already null, so newHead is null and the method correctly reports the empty list. No separate branch is needed.

Dry run on 1 -> 2 -> 3:

step head newHead list seen from newHead
null check [1] - -
read next [1] [2] 2 -> 3
detach [1] -> null [2] 2 -> 3
return - [2] 2 -> 3

As with insertion at the head, the caller must store the result: head = deleteHead(head);. A call whose return value is dropped leaves the caller’s variable pointing at the detached node, and the list appears to have shrunk to one element.

Deleting the tail, for contrast

Intuition. Deleting the first node is O(1) because the head is where we start. Deleting the last node is O(n) because we must find the node before it: a singly linked list has no backward link, so the second-last node can only be reached by walking from the head. Once we have it, we cut its next.

Algorithm.

  1. If the list is empty or has one node, the result is the empty list; return null.
  2. Walk temp from the head while temp.next.next != null. It stops on the second-last node.
  3. Set temp.next = null and return the unchanged head.
static ListNode deleteTail(ListNode head) {
    if (head == null || head.next == null) return null;     // empty or single node: the list becomes empty
    ListNode temp = head;
    while (temp.next.next != null) temp = temp.next;        // stop on the second-last node
    temp.next = null;
    return head;
}

Complexity. Time O(n), space O(1).

The guard in step 1 is what makes temp.next.next safe: after it, the list has at least two nodes, so temp.next is never null on the first iteration, and the loop keeps temp.next non-null by stopping as soon as temp.next.next is null. Removing that guard turns a two-line loop into a NullPointerException on a one-node list. Doubly linked lists make this operation cheaper to write (the prev link gives the second-last node for free once you have the tail), but still O(n) unless a tail reference is maintained.

Generalisation: delete the k-th node

Intuition. Deleting the head is the k = 1 case of deleting the k-th node (1-based). For any other k, the node must be bypassed: node k - 1 has to point at node k + 1. So we walk to node k - 1, check that a k-th node actually exists, and redirect one link. The head is special only because there is no node k - 1 to redirect.

Algorithm.

  1. If the list is empty or k < 1, return the list unchanged.
  2. If k == 1, return deleteHead(head).
  3. Walk prev from the head for k - 2 steps so it stops on node k - 1, bailing out if it becomes null.
  4. If prev or prev.next is null, there is no k-th node; return the head unchanged.
  5. Set prev.next = removed.next, detach removed, and return the head.
static ListNode deleteAtPosition(ListNode head, int k) {
    if (head == null || k < 1) return head;
    if (k == 1) return deleteHead(head);
    ListNode prev = head;
    for (int i = 1; i < k - 1 && prev != null; i++) prev = prev.next;    // stop on node k - 1
    if (prev == null || prev.next == null) return head;                  // there is no k-th node
    ListNode removed = prev.next;
    prev.next = removed.next;                                             // bypass the k-th node
    removed.next = null;
    return head;
}

Complexity. Time O(k), so O(1) for the head and O(n) for the tail. Space O(1).

The test file runs deleteAtPosition(list, 1) against deleteHead and deleteAtPosition(list, n) against deleteTail on every input, so the three methods are checked against identical expected outputs. It also checks that k = n + 1 and k = 0 leave the list exactly as it was.

Edge cases and pitfalls