pattern heroPT–23LeetCode Extension

Linked list pointers

List nodes are joined by links, so you change a list by re-linking, not by moving data: adding or removing a node is one action. The key is not to lose the rest of the list when you overwrite a link.

Variant
P12 Linked list pointersReverse · 1×

Example problem: reverse the linked list 5 → 1 → 8 → 3 → 6 in place, without making new nodes.

nonenone51836headprev
not reached yetcurnext, savedreversed, starts at prev

prev = none: the reversed part is empty, so it ends in none

prev = nonecur = –next = –
01/29
restart · back · play · step
Speed
1function reverse(head):
2 prev = none
3 cur = head
4 while cur is not none:
5 next = cur.next
6 cur.next = prev
7 prev = cur
8 cur = next
9 return prev

← → step · space play/pause

How to recognise

a linked list that must be reversed (whole, a part, or in groups of k), merged, split, reordered or cleaned of some nodes, in place; or a cache that moves items to the front, like LRU (a hash map plus a doubly linked list).

How to solve problems like this

  1. Draw the nodes and arrows before and after. Name every pointer you must keep so nothing gets lost.
  2. Before you overwrite a .next, save the node it points to.
  3. Rewire in a fixed order, then move each pointer one step. Check the first node, the last node and an empty list.
  4. To reverse only a part (positions left..right, or each group of k), stop at the node before it, reverse the part with the same loop, then connect both ends back.

Variant: Dummy head

The same, but put an empty placeholder node before the head. Then the first node is like any other and needs no special case.

  1. Reach for a dummy whenever the head itself may change: merging, removing nodes from the front, splitting into parts.
  2. Keep tail on the last node of the answer and only ever append after it: tail.next = node, then tail = tail.next.
  3. Move the pointer of the list you took from. When one list runs out, attach the rest of the other in one step.
  4. Return dummy.next. To partition a list or drop duplicate runs, build one or two answers with their own dummies and join them at the end.

Where it's used

  • The Linux kernel. The kernel keeps processes, open files and much more in linked lists (struct list_head). Taking a process off a queue means re-linking two links, with nothing moved.
  • memcached. Entries sit in a doubly linked list from recently used to long unused. A used entry is moved to the front, and when memory runs out, the tail is dropped.
  • Memory allocation. malloc in glibc keeps free chunks of memory in linked lists. Freeing a chunk links it into a list; allocating one unlinks it.