Linked List

Linked list problems are rarely about clever algorithms. They are about not losing your place. Almost every one comes down to careful pointer reassignment, and almost every bug is a link you overwrote before you were finished with it.

What you give up, and what you get#

An array gives you random access: element k is one arithmetic step away. A linked list gives that up entirely — reaching the k-th node means walking k links. In exchange you get O(1) insertion and removal given a pointer to the right place, without shifting anything.

That trade decides which problems show up. You will not be asked to sort a list by index or binary search it. You will be asked to splice, reverse, merge, or detect structure — all things that are cheap when you only ever need the node in front of you.

Two consequences worth internalising:

• You cannot go backwards. A node knows its successor and nothing else. Any algorithm that needs the previous node must carry it along in a variable.
• You only get one pass cheaply. Walking the list twice is legal and often fine, but the elegant solutions usually find a way to do it in one.

Reversal#

This is the operation people cannot picture, and the reason is almost always the same: they try to move forward after breaking the link that told them where forward was.

Step through it slowly. Each iteration does exactly two things, in this order: save the next node, then rewire. Swap those and the list is severed — you are holding a node whose next now points backwards, with no way to reach the rest.

prev = null
curr = head

while curr is not null:
    next = curr.next     // save it BEFORE breaking the link
    curr.next = prev     // rewire: point backwards
    prev = curr          // shuffle both pointers forward
    curr = next

return prev              // curr fell off the end; prev is the new head

The invariant is that everything from prev backwards is already reversed and everything from curr onwards is untouched. The loop ends when curr runs off the end, at which point prev is standing on the last node — which is now the first.

Note the return value. Returning head returns a pointer to what is now the tail, whose next is null: a one-element list. It is the most common way to get this wrong.

The dummy head#

When a function builds or filters a list, the first node is a special case: there is no previous node to attach it to. That special case infects the whole function with if the result is empty checks.

The fix is to invent a node that is never part of the answer:

dummy = new Node()       // a placeholder, discarded at the end
tail = dummy

while there is more to append:
    tail.next = next node to take
    tail = tail.next

return dummy.next        // the real head, whatever it turned out to be

Now every append is identical, including the first, and you never need to ask whether the result is empty. Merging two sorted lists is exactly this loop with a comparison choosing which list to take from — and because both inputs are already sorted, taking the smaller head each time is enough.

Two pointers on a list#

Because you cannot index, several array techniques reappear as pointer tricks. See two pointers for the general shape; the list-specific versions are:

• Fast and slow. Advance one pointer two nodes for every one of the other. When the fast pointer reaches the end, the slow one is at the midpoint — in a single pass, without counting the length first.
• Cycle detection. The same pair, but if the list loops, the fast pointer eventually laps the slow one and they meet. If there is no cycle, fast simply reaches null. This is O(1) space, where the obvious solution uses a set of visited nodes.
• Gap of k. Start one pointer k nodes ahead. When it hits the end, the other is k from the end — the one-pass way to find the k-th-from-last node.

Checking whether a list is a palindrome combines all three ideas: find the middle with fast/slow, reverse the second half in place, then walk the two halves in step. It is O(1) space and it is worth doing once by hand, because it uses every technique on this page.

Recognising it#

Common signals and the standard response:

• “Without extra space” — you are meant to rewire nodes rather than copy them into an array. Reversal and cycle detection are the usual targets.
• “In one pass” — a second pointer, either running ahead by a fixed gap or at double speed.
• The head might change — use a dummy head and return dummy.next.
• You need the previous node — carry it in a variable; the list will not give it to you.

If you are stuck, copying the values into an array is a perfectly good first answer. Say the space cost out loud, get something working, then ask whether pointers alone would do.

Summary#

The data structure is trivial and the algorithms are short. What makes these problems is sequencing: save before you overwrite, keep the node you will need next, and decide up front whether the head can change. Draw four boxes and move the arrows by hand once — after that, the code writes itself.