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

Leave a Reply

Your email address will not be published. Required fields are marked *