Linked Lists

1The mental model (what this really is)#

A linked list is a chain, and there is no magic in it.

• Each link is a node holding a value and a reference (a pointer) to the next node.
• That is the entire data structure.

node = { val, next } # next points to another node, or null

You lose random access by index.

• You cannot jump to the 5th element in O(1) the way arr[5] would.
• You walk: node, node.next, node.next.next.
• Everything is sequential, so reaching index k costs k steps.

What you get in return is cheap insertion and deletion.

• If you already hold a pointer to a node, you splice in or cut out by rewiring one or two next fields. That is O(1).
• No shifting a million elements the way inserting at the front of a big array would force.

So the entire game is pointer rewiring. Every problem is really the same question.

• Which pointers do I need to hold, and in what order do I reassign them so I never lose a piece of the chain?
• Lose the reference to a node and the whole rest of the list after it is unreachable, which in a garbage-collected language means it is gone.
• That is the core tension, and it is why order of assignment matters so much.

Two mental habits that pay off immediately:

• Draw it. Three or four boxes with arrows, always. Even senior people draw it, and interviewers read the drawing as a signal that you think structurally.
• Treat null as a real place, not an absence. The end of the list is a value you point at. Roughly half the bugs I see come from one thought: "I forgot the list can end right here."

Here is the shape to keep in your head for a four-node list.

2How to recognize it (the signals in a problem)#

The useful skill is spotting which technique the problem wants in the first 30 seconds, before you write anything.

• "Reverse the list" or "reverse part of it" means iterative pointer reversal. The three-pointer dance: prev, curr, next.
• "Find the middle," "detect a cycle," "find where the cycle starts," or anything about a loop means fast and slow pointers (Floyd's tortoise and hare). The moment you read "cycle," your hand should already be writing slow and fast.
• "Nth from the end" or "remove the Nth from the end" means two pointers with a fixed gap, so one pass instead of two.
• "Merge two lists" or "add two numbers" means a dummy head and a tail pointer you keep appending to.
• "Reorder," "partition," "group odd and even positions" usually means split the list into pieces, operate on each piece, then stitch them back together.

Internalize those five mappings and you have covered maybe 80 percent of what gets asked in real loops. The remaining 20 percent is usually one of these five with a twist, like reversing in groups instead of reversing the whole thing.

3The template (how it works, with pseudocode)#

Three templates carry most of the weight. Learn these cold, to the point where you write them without thinking, so your brain is free for the actual problem.

Template A: iterate and rewire (the reversal pattern).

prev = null
curr = head
while curr is not null:
 nxt = curr.next # save the rest before we lose it
 curr.next = prev # flip the arrow backward
 prev = curr # advance prev
 curr = nxt # advance curr
return prev # prev is the new head

• The saved nxt is the whole trick: grab the next node before you overwrite curr.next, or the tail vanishes on the very first iteration.
• Say the four lines out loud in order while you write them: save, flip, advance prev, advance curr.
• The order is not negotiable.

Template B: fast and slow pointers.

slow = head
fast = head
while fast is not null and fast.next is not null:
 slow = slow.next
 fast = fast.next.next
# when loop ends, slow is at the middle
# if fast ever meets slow again, there's a cycle

• Fast moves two steps per one of slow, so when fast reaches the end, slow is exactly halfway.
• If the list loops, fast eventually laps slow and they collide at the same node.
• The loop condition checks both fast and fast.next, because fast.next.next blows up if either is null. Getting that condition wrong is the single most common crash in this template.

Template C: dummy head.

dummy = new Node() # a fake node before the real head
tail = dummy
while ... :
 tail.next = someNode
 tail = tail.next
return dummy.next # skip the fake, return the real head

• The dummy removes an entire class of special cases.
• Without it you scatter if head is null branches and "is this the first node?" checks everywhere, and one of those branches will have a bug.
• With it, the first real node runs the exact same code as every other node.
• Use it whenever you build a new list or might delete the head. One extra node buys you ten fewer lines of edge-case handling, a trade I take every time.

4A worked example (walk through one problem step by step)#

Remove the Nth node from the end of the list. This one best teaches the pattern.

• List: 1 -> 2 -> 3 -> 4 -> 5, N is 2.
• We want to delete the 4 and get 1 -> 2 -> 3 -> 5.

Why not the obvious two-pass version.

• Walk once to count the length L, then walk again to position L - N and unlink.
• It works and it is O(n).
• But the cleaner answer, the one interviewers lean toward when they say "can you do it in one pass," is a single traversal with two pointers held a fixed distance apart.

The reasoning.

• Put a fast pointer N nodes ahead of a slow pointer. When fast hits the end, slow is sitting exactly N nodes from the end.
• That is the node I care about. But to delete a node in a singly linked list you need the node just before it.
• So I set the gap to N+1 and slow lands one node earlier, on the predecessor.

Step one: dummy node in front of the head.

• N might equal the length, meaning we delete the head itself.
• The dummy lets us handle that without a special branch.

dummy -> 1 -> 2 -> 3 -> 4 -> 5

Step two: point both fast and slow at dummy, then advance fast by N+1 steps (3 here).

• fast moves to node 2.
• The gap is now N+1 nodes, which means slow will stop one before the target.

Step three: move both pointers one step at a time until fast falls off the end.

• fast at 2, slow at dummy. Step.
• fast at 3, slow at 1. Step.
• fast at 4, slow at 2. Step.
• fast at 5, slow at 3. Step.
• fast is null. Stop. slow is at 3.

Step four: rewire.

• slow points at 3, and 3.next is 4, the node to delete.
• slow.next = slow.next.next makes 3 point straight to 5, and node 4 is unlinked.

dummy -> 1 -> 2 -> 3 -> 5

• Return dummy.next, which is 1. Done in a single pass, O(n) time and O(1) space.

What the dummy bought us.

• If the list were 1 -> 2 and N were 2, we would be deleting the head.
• With the dummy, fast advances 3 steps past dummy and falls off immediately, so slow ends on the dummy itself.
• slow.next = slow.next.next correctly makes dummy -> 2, and we return dummy.next, which is 2.
• No special case, no "if we are deleting the head" branch. That is the entire reason the dummy is there.

5Variations and gotchas#

Reverse in groups of K (Reverse Nodes in k-Group).

• Same reversal pattern as Template A, but you reverse exactly K nodes, stop, reconnect to the previous group's tail, and repeat.
• The reconnection is where people lose the thread. Keep a pointer to the tail of the group you just finished, because after you reverse the next group, that old tail has to point at the new group's head.
• A leftover chunk smaller than K at the very end usually stays as-is.

Finding the start of a cycle (Linked List Cycle II).

• After fast and slow collide inside a loop, reset one pointer to the head and move both one step at a time. They meet at the cycle's entry node.
• It feels like a trick, but it falls out of the math: if the distance from head to the entry is a and the collision happens inside the loop, then a equals the distance from the collision point to the entry measured forward around the loop.
• So walking both at speed 1 from head and from the collision point lands them together at the entry.

Merge and sort.

• Merging two sorted lists is pure dummy-head work: compare the two front nodes, append the smaller, advance, repeat.
• Merge-sort on a list uses the slow/fast middle-finder to split in half, recurses, then merges, which gives O(n log n) time.
• Be ready to explain how both halves connect.

Doubly linked lists.

• Each node also has a prev. These power LRU caches, where you need O(1) removal from the middle given a pointer to the node, something a singly linked list cannot do.
• Different flavor, same pointer discipline, just twice the arrows to keep consistent.
• The usual pairing is a doubly linked list for order plus a hash map for O(1) lookup, which is exactly the LRU Cache design.

The gotchas that bite everyone:

• Losing the rest of the list by overwriting next before saving it. The number one cause of a silently broken answer.
• Off-by-one in the pointer gap. Is it N steps or N+1? Trace the tiny 1 -> 2, N=2 example to be sure before you commit.
• Forgetting the list can be empty (head is null) or a single node. Both should pass without a crash.
• Creating a cycle by accident when rewiring, then hanging in an infinite loop. If your test never terminates, you almost certainly pointed a node back at an earlier one.

6Complexity#

Most solutions are O(n) time.

• You traverse the list a constant number of times, usually once or twice.
• The two-pointer tricks let you do in one pass what looks like it needs two. That is elegant but does not change the big-O: O(2n) and O(n) are the same class.

Space is usually O(1), and that is the selling point.

• You hold a handful of pointers, no extra structure that grows with the input.
• It is often an explicit constraint in the prompt.
• If you reach for a hash set (say, detect a cycle by storing every node seen), it works and it is correct, but it is O(n) space, and the interviewer is almost always fishing for the O(1) fast/slow version.

The move that scores on the space trade-off:

• State the hash approach in one sentence.
• Name its O(n) space cost.
• Then say "but we can do O(1) with fast and slow" and write that.
• You show range and land on the better answer.

Why quicksort is the wrong sort here.

• Random access is O(n) and indexing is painful, which is why you rarely see "sort this list with quicksort" asks.
• Quicksort needs cheap random access for partitioning, the structure does not support it.
• So merge sort is the natural sort for lists.

7Mistakes that cost people the round#

• Not drawing it. The single biggest predictor of failure I see. People hold five pointers in working memory, drop one, and never recover. Boxes and arrows on the whiteboard or shared doc, updated as you reassign.
• Skipping the dummy head. They write ten lines of special-case handling for the head, introduce a bug in one branch, and spend the back half of the round debugging it. The dummy would have erased all of it.
• Not testing the edges out loud. Empty list. One node. Two nodes. The target being the head or the tail. Walk at least two of these before you say you are done. Interviewers notice and score when you self-check unprompted.
• Overwriting before saving. The classic curr.next = prev without first stashing curr.next into nxt. Instant lost list, and it usually passes a tiny test by luck and fails on length 3.
• Going silent while pointer-juggling. You look stuck even when you are fine. Narrate: "I am saving next, now flipping the arrow, now advancing prev, now advancing curr." It keeps the interviewer with you and often catches your own mistake one word before you type it.

8Your practice path (named problems by difficulty)#

Do them in this order. Each one teaches a specific muscle, and the order builds on itself.

Warm up (Easy):

• Reverse Linked List (Template A, the one everything else builds on)
• Middle of the Linked List (Template B, fast and slow)
• Merge Two Sorted Lists (Template C, dummy head)
• Linked List Cycle (Template B, the detect half)
• Remove Duplicates from Sorted List (plain traversal with careful unlinking)

Core (Medium):

• Remove Nth Node From End of List (the worked example above)
• Linked List Cycle II (find the cycle entry, the Floyd math)
• Add Two Numbers (dummy head plus carry handling)
• Odd Even Linked List (split, operate, stitch)
• Reorder List (middle-find, reverse second half, merge the two)
• Partition List (two dummy lists, then join)
• Rotate List (find length, close the ring, cut)
• Swap Nodes in Pairs (reversal in groups of 2)
• Copy List with Random Pointer (interleave-and-split, or hash map)

Stretch (Hard):

• Reverse Nodes in k-Group (Template A generalized to K)
• Merge k Sorted Lists (Merge Two Sorted Lists plus a heap, or pairwise merge)
• LRU Cache (doubly linked list plus a hash map)

If you only have time for five: Reverse Linked List, Linked List Cycle II, Remove Nth Node From End, Merge Two Sorted Lists, and Reorder List. Those five touch every template on this page, and Reorder List alone forces you to chain three of them in one problem.

Reorder List is the whole page in one problem: find the middle, reverse the back half, then merge. Nail it and you have nailed all three templates at once.

9Where this shows up#

• Linked lists are a staple of phone screens and the first one or two coding rounds at most large companies.
• Amazon, Microsoft, Google, and Meta all lean on them as warmups.
• LRU Cache specifically is a near-rite-of-passage at several of them, common enough at Amazon and Meta that you should expect it rather than be surprised by it.
• Startups use them to filter early because they are fast to pose and quick to grade.
• They are rarely the final boss of an onsite, but they are very often the gate you walk through first.

Why fumbling one looks worse than fumbling something harder.

• Everyone expects you to clear it clean.
• A sloppy reverse-a-list makes an interviewer quietly worried about everything that comes after.
• Treat them as free points, because that is what they are for a prepared candidate.

With the three templates above and the habit of drawing every single time, they become exactly that: the easy 15 minutes that lets you spend the rest of the loop on the genuinely hard stuff.

Want to see which rounds actually use this? Check the company guides to find where linked list questions tend to appear.