Deletion at the end of a Linked List

Given the head of a singly linked list, delete the tail — the last node — and return the head of the modified list.

The tail is the only node whose next pointer is null. Removing it means the node just before it becomes the new last node, so its next must be set to null.

If the list has a single node, deleting it leaves an empty list, so you return a null head.

Hints

· Stuck? Reveal one nudge at a time.

To remove the last node, ask yourself: which node's next pointer actually has to change?

You cannot touch the tail directly — you need the node right before it, and a singly linked list has no backward pointer.

Walk one pointer forward until curr.next.next is null; curr is now the second-last node, so set curr.next to null.

Common doubts

The head is directly available, but the tail's predecessor is not — a singly linked list has no backward pointer, so you must walk from the front to reach it, which is O(n).

Deleting that single node leaves an empty list, so you return null (an empty head).

You want to land on the node just before the tail. If you walk until curr.next is null, you have gone one step too far and are standing on the tail itself, with nothing left to cut.

Interview follow-ups

· What an interviewer asks next.

Use two pointers k apart, then advance both until the front one hits the end — the trailing pointer lands on the node before the target, ready to splice it out in one pass.

With a backward pointer (or a maintained tail pointer) you reach the last node's predecessor in O(1), so deleting the tail becomes constant time instead of O(n).

Fun facts

Deleting the tail of a singly linked list is O(n), but the same operation on a doubly linked list (or one that caches a tail pointer) is O(1) — the extra backward link pays for itself.
This 'walk to the second-last node' pattern is the seed of the two-pointer trick used to remove the n-th node from the end in a single pass.

Asked at

AmazonMicrosoftAdobe

Frequently Sometimes Occasionally

Example 1

Input: head = [1, 2, 3, 4, 5]
Output: 1 -> 2 -> 3 -> 4
The last node (value 5) is removed, leaving 1 -> 2 -> 3 -> 4.

Example 2

Input: head = [3, 12, 9]
Output: 3 -> 12
Dropping the tail node (value 9) leaves 3 -> 12.

Constraints

- 1 <= number of nodes <= 10^5 - 1 <= node value <= 10^5

Deleting the head of a linked list is a one-line trick. Deleting the tail is its deceptively harder sibling: a singly linked list has no backward pointer, so to remove the last node you must first find the node in front of it. That single asymmetry — the front is instant, the back needs a walk — is the whole lesson.

Prerequisites

Before you start

· Concepts used directly in the solution.

Singly linked list. A chain of nodes where each stores a value and a next pointer; the last node's next is null.

One-directional traversal. You can only move forward via next — there is no pointer back to the previous node, so reaching a predecessor means walking from the head.

Pointer reassignment. Setting a node's next to null detaches everything after it — that is how you drop the tail.

Understand the problem

In plain terms: the new tail is the second-to-last node. Walk to it, set its next to null, and return the original head unchanged.

Worked example — head = [1, 2, 3, 4, 5]

before:  head -> [1] -> [2] -> [3] -> [4] -> [5] -> null
                                       ^      ^ delete this (tail)
                                 second-last

walk:    stop at [4], the node whose next.next is null
cut:     [4].next = null

after:   head -> [1] -> [2] -> [3] -> [4] -> null
answer:  1 -> 2 -> 3 -> 4

Clarifying questions

Confirming the input's shape before moving a single pointer is what separates a careful engineer from a fast one — with lists, a wrong emptiness assumption is exactly where the crash hides.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Is the list guaranteed to have at least one node?”

The constraints promise at least one node, so head is never null on input — worth confirming so you know the empty-input branch cannot happen.

Edge cases

“What should I return if the list has exactly one node?”

Deleting the only node leaves an empty list, so the answer is a null head — the case people most often miss.

Constraints and scale

“How large can the list get?”

Up to 100000 nodes, so a single linear pass is fine but anything quadratic is not.

The ideal opening — say it like this

Before I code, let me confirm the shape of the input.

The constraints guarantee at least one node, so head is never null to begin with — correct?

And if there is exactly one node, deleting the tail returns an empty list, meaning a null head.

Key observations

1Aha

The tail's predecessor is what you actually need

You do not remove the last node by reaching it — you remove it by reaching the node before it and nulling its next. In a singly linked list there is no backward pointer, so that predecessor can only be found by walking forward from the head.

head -> [A] -> [B] -> [C] -> null
                       ^ tail
                 ^ find this node and cut after it

2Aha

Stop when the next node is the tail

Walk a pointer curr forward while curr.next.next is not null. The moment it is null, curr sits on the second-last node — the tail is curr.next. Set curr.next = null and you are done.

3Aha

The single-node list is special

If the list has just one node, it has no predecessor to walk to, so deleting it must return null. Guard this case up front so curr.next.next never dereferences a null pointer.

Brute force vs optimal

	Count then cut	Single pass
Idea	First pass counts n; second pass walks to node n-2 and cuts	Walk one pointer until its next is the tail, then cut
Passes	2	1
Time	O(n)	O(n)
Space	O(1)	O(1)

Both are linear, but the single pass reaches the tail's predecessor with one traversal instead of two — see the full code in the Approaches selector below.

Summary

Key takeaway

To delete the tail of a singly linked list you must find its predecessor: walk to the second-last node and set its next to null. Because there is no backward pointer, this costs one linear pass — unlike head deletion, which is O(1).

if head is null or head.next is null: return null
curr = head
while curr.next.next is not null:
    curr = curr.next
curr.next = null        # (free curr.next in manual-memory languages)
return head