Partition List

Partition List

What is this problem about?

The Partition List problem asks you to rearrange a linked list such that all nodes with values less than x come before nodes with values ≥ x, while preserving the original relative order within each group. This Partition List coding problem uses the two-pointer split-and-merge technique. The linked list and two pointers interview pattern is directly demonstrated.

Why is this asked in interviews?

Apple, Microsoft, Meta, Amazon, Google, Bloomberg, and Adobe ask this because it tests stable linked list partitioning with two separate lists. It's analogous to the stable partition of an array but applied to linked lists, requiring careful pointer manipulation.

Algorithmic pattern used

Two dummy heads + merge. Create two dummy nodes: lessHead and greaterHead. Scan the original list: if node.val < x, append to less list; otherwise append to greater list. Connect the two lists: lessHead_tail.next = greaterHead.next. Return lessHead.next.

Example explanation

list=1→4→3→2→5→2, x=3. (values < 3 go before, ≥ 3 go after) Less list: 1→2→2. Greater list: 4→3→5. Merge: 1→2→2→4→3→5. Result: 1→2→2→4→3→5.

Common mistakes candidates make

• Not setting the tail of the greater list's next to null (creates a cycle).
• Losing nodes by not properly updating pointers.
• Using the original list pointers (creates shared pointers and corruption).
• Off-by-one: condition is < x, not <= x.

Interview preparation tip

Partition List uses the "dual dummy head" pattern — the cleanest approach for list partitioning. Create dummy nodes for each group, append to appropriate group, then connect. Always null-terminate the last group. This pattern extends to "k-way list partition" and "group by property" linked list problems. The dummy node trick eliminates edge cases for empty groups.