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**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
Node partitionListV2(Node head, int a){ Node n = head; // We'll need the concept of three lists. LessThanList, EqualsList, GreaterThanList // define start and end pointers for my 3 lists Node startOfLTList = null; Node endOfLTList = null; Node startOfEqList = null; Node endOfEqList = null; Node startOfGTList = null; Node endOfGTList = null; while (n != null) { //preserve next value so that loop can iterate Node next = n.next; n.next = null; if ((n.data < a)) { if (startOfLTList == null){ startOfLTList = n; endOfLTList = startOfLTList; } else { endOfLTList.next = n; endOfLTList = n; } } else if (n.data == a) { if (startOfEqList == null){ startOfEqList = n; endOfEqList = startOfEqList; } else { endOfEqList.next = n; endOfEqList = n; } } else { if (startOfGTList == null){ startOfGTList = n; endOfGTList = startOfGTList; } else { endOfGTList.next = n; endOfGTList = n; } } n = next; } // merge lists together. Omit LTList or EQList pointers if they are empty; if (startOfLTList == null && startOfEqList == null){ return startOfGTList; } else if(startOfLTList == null){ endOfEqList.next = startOfGTList; return startOfEqList; } else if(startOfEqList == null){ endOfLTList.next = startOfGTList; return startOfLTList; } else { // neither LT or EQ list is empty endOfLTList.next = startOfEqList; endOfEqList.next = startOfGTList; return startOfLTList; } } |

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