Partition List

Medium#86dummy head

You get a linked list and a number x. Reorder the nodes so that all nodes with values under x come before the nodes with values x or more, and inside each group the nodes keep their order. Return the head. Our example: 6 → 1 → 9 → 4 → 2, x = 5 — the answer is 1 → 4 → 2 → 6 → 9.

86 Partition ListWalkthrough · 1×

Example: 6 → 1 → 9 → 4 → 2, x = 5. The old list is on top; nodes under 5 move to the middle row, the rest to the bottom row.

nonelessHeadmoreHead61942less
not reached yetnodeunder 55 or morethe answer

A dummy node for the nodes under 5: lessHead. less is the last node of that list, for now the dummy itself

01/34
restart · back · play · step
Speed
1function partition(head, x):
2 lessHead = new node; less = lessHead
3 moreHead = new node; more = moreHead
4 node = head
5 while node is not none:
6 if node.val < x:
7 less.next = node
8 less = node
9 else:
10 more.next = node
11 more = node
12 node = node.next
13 more.next = none
14 less.next = moreHead.next
15 return lessHead.next
state
node
–
less
lessHead
more
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Each node goes to the end of its list, in the order the old list gives them, so both groups keep their order.
  2. The two dummies mean an empty list needs no check: with no node under x, lessHead.next simply becomes the first node of the other list.
  3. Nodes are moved, not copied, so the last node of the more list keeps its old next. more.next = none cuts it before the lists are joined; without that the answer loops.

Complexity

Time O(n): one pass, each node is moved once. Memory O(1): the nodes are reused, only the two dummies are new.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.