Linked list pointer rewiring

When to use it

Use it when the answer is the same nodes in a different order or grouping, built by changing links as you walk the list.

It belongs to the foundations group: Remember what you have seen, in a shape that makes the next question take one step.

Watch it work

A bakery keeps its orders in a linked list, in the order they came. Each number is how many loaves an order asks for. Move every order under limit loaves to the front. Inside each group, keep the order of arrival.

Input
head = [3, 8, 1, 9, 6, 2]
limit = 5

Output
[3, 1, 2, 8, 9, 6]

head reaches the code as a linked list: each node has a value, val, and a link to the node after it, next.

The method

1. Start two empty chains, each behind a placeholder node
2. Attach each node to the tail of the chain it belongs to
3. End the large chain: its tail may still hold an old link
4. Join the chains: the small tail points at the first large node
5. The answer starts right after the small placeholder

The run, one moment at a time

1. Step 1. A placeholder node is an extra node that is not an order. Two of them each start an empty chain, so the first order is attached the same way as every later one. Top: orders under 5. Bottom: the rest.
2. Step 2. 3 is under 5. The small chain is empty, so its placeholder points at 3. 3 is now the small tail, the last node of that chain.
3. Step 2. 8 is 5 or more. The large chain is empty, so its placeholder points at 8. 8 is the new large tail. The old link from 3 to 8 stays until it is changed.
4. Step 2. 1 is under 5. The small tail, 3, stops pointing at 8 and points at 1. 1 is the new small tail.
5. Step 2. 9 is 5 or more. The large tail, 8, stops pointing at 1 and points at 9. 9 is the new large tail.
6. Step 2. 6 is 5 or more. The large tail, 9, already points at 6, so that link stays. 6 is the new large tail.
7. Step 2. 2 is under 5. The small tail, 1, stops pointing at 9 and points at 2. 2 is the new small tail.
8. Step 3. 6 is the last large order, but it still pointed at 2, a link left from the old list. Point it at nothing, or the list would never end.
9. Step 4. Join the chains: 2, the small tail, points at 8, the first large order. One list now holds every order.
10. Step 5. After the small placeholder the list reads 3, 1, 2, 8, 9, 6. No order was moved or copied: 5 of the 6 orders had their link pointed somewhere new.

The code

The numbered comments are the steps of the method.

function solve(head, limit) {
  // 1. Start two empty chains, each behind a placeholder node
  const small = { val: 0, next: null };
  const large = { val: 0, next: null };
  let smallTail = small;
  let largeTail = large;
  let node = head;
  while (node) {
    // 2. Attach each node to the tail of the chain it belongs to
    if (node.val < limit) {
      smallTail.next = node;
      smallTail = node;
    } else {
      largeTail.next = node;
      largeTail = node;
    }
    node = node.next;
  }
  // 3. End the large chain: its tail may still hold an old link
  largeTail.next = null;
  // 4. Join the chains: the small tail points at the first large node
  smallTail.next = large.next;
  // 5. The answer starts right after the small placeholder
  return small.next;
}

def solve(head, limit):
    # 1. Start two empty chains, each behind a placeholder node
    small = ListNode(0)
    large = ListNode(0)
    small_tail = small
    large_tail = large
    node = head
    while node:
        # 2. Attach each node to the tail of the chain it belongs to
        if node.val < limit:
            small_tail.next = node
            small_tail = node
        else:
            large_tail.next = node
            large_tail = node
        node = node.next
    # 3. End the large chain: its tail may still hold an old link
    large_tail.next = None
    # 4. Join the chains: the small tail points at the first large node
    small_tail.next = large.next
    # 5. The answer starts right after the small placeholder
    return small.next

How to spot it

Given: A linked list, and you may relink its nodes

A node is reached only by following links. Putting nodes in a new order means changing those links, not shifting values as in an array.

Asked: Return the same nodes in a new order

No new node is needed. Each node keeps its value, and only its link is pointed somewhere else.

Asked: Join two lists into one, or cut one list into parts

A join or a cut is one link changed: the end of one part points at the start of another, or at nothing.

Limits: Reorder the list in place, with only a few variables

Changing links in place needs a few variables that each remember one node, and nothing more.

Looks like it, but is not

• You must find the middle node, or tell whether the list loops back on itself. Use Fast and slow pointers. Those questions ask where a node is. Two markers moving at different speeds answer them without changing a link.
• The values are in an array and you must reverse them or put them in a new order. Use Opposing two pointers. An array lets you reach any position at once, so you swap values from both ends. There are no links to change.

Cost and mistakes

Time is about n steps for n nodes, written O(n): the list is walked once and each node gets at most one new link. Extra space is two placeholder nodes and a few variables, written O(1), because no node is copied.

Watch out

• A link you never change keeps its old target. Point the last node of the new list at nothing, or the list can lead back into itself and never end.
• Before you point a link somewhere new, make sure a variable still holds the node it pointed at. If that link was the only way to the node, the node and everything after it are lost.

In the 150

5 problems of the 150 use it. Naming them gives their method away, so the list is folded.