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

 

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