Hi There,

I’m Andrae, a Software Developer. I love sharing things that I have learned, and things that work efficiently. I’ve shared some programming posts here. Hopefully you find it helpful. Free free to leave a comment.

Check out my most recent blog post:

Partition a Linked List by Value X (part 2)

To expand on the problem here Partition Linked List Based on value x

I now asked this question.

Partition a Linked List by a value x, so that values less than x come first, values equal to x come next, and values greater than x come last. Note: Retain relative order.

Unlike the previous question, this one has no shortcuts that were obvious to me.

To solve this problem, I need the concept of 3 lists. LessThanList (LTList), EqualToList (EqList), and GreaterThanList (GTList).

Because we are doing this in place and are working with linked list, it’s sufficient to just move around pointers without actually creating new lists.

So the pointers will track the beginning and end of their respective list.

startOfLTList, endOfLTList,

startOfEqList, endOfEqList,

startOfGTList, endOfGtList



So for an input of 4, 3, 6, 5, 2

We get an output of 3, 2, 4, 6 ,5

Where the partitions are 3, 2,| 4, | 6 ,5