Linked list patterns

The idea#

Picture a treasure hunt made of paper slips. Each slip holds a prize and the name of the next hiding spot. You can tape a new slip between two others, and the rest of the hunt stays put. To read the fifth prize, you still start at the first slip and walk.

You do pointer surgery: insert or delete is O(1) once you are holding the node, reaching that node is O(n), and almost every routine on the sheet is O(n) time and O(1) extra space, with the recursive reverse spending O(n) on the call stack.

A node is a small object: a value, and a next that is another node or null. The list you can find is the first node, the head. There is no index. Drop the head and the later slips are still tied together, and you have no way back to them.

Splicing means you change one or two next fields. A reverse walks with three fingers: previous, current, and next. Save next, point current back at previous, step forward. A dummy head is a sentinel node that is not part of the answer. It gives you a stable hook when the real head might be the node you cut.

Two pointers can share one walk. Fast takes two steps, slow takes one, and when fast falls off the end, slow is on the middle. Give them a fixed gap and slow stops just before the node you want to cut. Floyd's tortoise and hare uses those two speeds to meet inside a cycle, then one pointer goes back to the head and they walk in step until they meet at the entrance.

Why it matters#

An array is the right box until the job is "I am already holding this item, pull it out" or "open a hole right here." Opening a hole in an array shifts every later item, which is O(n). A list rewires two pointers and the other nodes stay where they are. The bill arrives when someone asks for the item at position 400. You walk 400 links. Random access is the trade.

Listen for "in place," "O(1) extra space," "cycle," "middle," "nth from the end," and "reorder." Those are pointer-walk problems. The tools are a dummy head, fast and slow, a gap of n, and a splice. If you copy the values into an array, you solved a different problem and you spent the memory the question asked you to keep.

You already use the shape. A playlist that drops the current song and stitches its neighbors is a list. An LRU cache, the box that forgets whatever you have not touched lately, is a doubly linked list plus a map. The map finds the node in O(1). The two links pull it out and park it at the front in O(1).

A small example#

function middleValue(head) {  let slow = head;  let fast = head;  while (fast && fast.next) {    slow = slow.next;    fast = fast.next.next;  }  return slow ? slow.val : null;} const list = { val: 1, next: { val: 2, next: { val: 3, next: null } } };const mid = middleValue(list);

mid is 2. Fast fell off after slow had taken one step. Same walk, two speeds, no second list.

What the code below is doing#

The sheet opens with ListNode, plus fromArray and toArray, so later checks can build a list and read it back.

Section 1 reverses with prev, cur, and a saved next, and returns prev. O(n) time, O(1) space. Section 2 reverses the rest first, then sets head.next.next = head and clears head.next. Same time, O(n) stack.

Section 3 finds the middle. On an even length, slow lands on the second of the two middle nodes. A tighter loop, stopping when fast cannot take two more steps, lands on the first middle. Section 4 detects a cycle and returns the entrance node. No cycle returns null.

Section 5 merges two sorted lists. A dummy head, always attach the smaller node, then append whichever list remains. O(n + m) time, O(1) space. Section 6 removes the nth from the end: dummy, two pointers with a gap of n + 1, and when fast hits null, slow.next is the node to splice out. That gap is what lets you delete the head. Section 11 walks a sorted list and skips next while the values match.

Section 7 reorders into first, last, second, second-to-last: first middle, reverse the second half, interleave. Section 8 checks a palindrome the same way, then compares halves. Section 9 adds two numbers stored in reverse, carrying while either list or the carry remains. Section 10 finds a shared node by jumping each pointer to the other head when it falls off, so both walk length a + b. Section 13 reverses in groups of k, leaves a short tail alone, and hooks each group's new head to the previous tail.

Section 12 is the doubly linked sketch and the LRU. Sentinels sit at both ends. remove and addFront are O(1) given the node. A map from key to node is how get and put find it. Over capacity, the node just in front of the tail sentinel is the one you evict.

When you talk about it, say this: a list is pointer surgery. O(1) to splice a node you are holding, O(n) to find it, and O(1) extra space when a few fingers on the links do the work.

Everything below is the demonstration. Same idea, written as code you can run.