Matsushita's Blog

Partition a Linked List around a value x


Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes larger than x or equal to x

How to Solve

First, I prepare two nodes that are beforeStart and afterStart. These nodes can be define the following that.

  • beforeStart: connect nodes less than x
  • afterStart: connect nodes larger than x or equal to x

So, I can partition each node into prepared nodes by traversing given linked list. After that, by merging tow nodes, we can return node we want to ask.

Source Code