Partition Linked List Based on value x

During my algorithm review I came across this problem.

Write an algorithm to partition a linked list around a value, x, so that all nodes less than x comes before all nodes greater than or equal to x.

I really like this problem, because it is being very generous and allows you to be very efficient. Here are some tips that will help you with getting  a full solution.

Tip 1 – A complete sort is not necessary. (smile)

You may immediately think you need to sort this linked list, but in actuality you don’t need to sort it completely. Sorting it would be very expensive and be far from the optimal solution.

Tip 2 – The items that are bigger than or equal to  x, can be in any order just as long as there is a clear partition.

I wrote a solution that seemed simpler than what I was seeing in my book and online. I wanted to share it here.

Example 1 (Bold and | signifies my partition)

Input:

Node values: 9, 2, 6, 4, 3
Partition: 4
Acceptable outputs: 2,3,| 4,9,6     3,2, | 4,6,9     3,2, | 9,4,6      2,3, | 9,6,4      3,2,|6,4,9    2,3,|6,94 

My solution written in Java

public class Node {
    Node partitionList(Node head, int a){
		
		// Immediately advance to second element.
		Node n = head.next;
		Node previous = head;
		
		while (n != null) {
			if ((n.data < a)) {
				// Move smaller node to head, keep previous, advance n
				previous.next = n.next;
				n.next = head;
				head = n;
				n = previous.next;
			} else {
				// advance both n and previous
				previous = n;
				n = n.next;
			}
			
		}
		
		return head;
   }
}

How it works on example.

linked list values: 9, 2, 6, 4, 3
partition number: 4

previous = 9
n = 2
n is less than 4, so send 2 to the beginning of list. Keep previous as is, and advance n.

——————–

linked list values: 2, 9, 6, 4, 3

previous = 9
n = 6

n is not less than 4, so advance previous and advance n.

————————

linked list values: 2, 9, 6, 4, 3

previous = 6
n = 4

n is not less than 4, so advance previous and advance n.

—————————

linked list values: 2, 9, 6, 4, 3

previous = 4
n = 3

n is less than 4, so send 3 to the beginning of list. Keep previous as is, and advance n.

————————

now n =  null, and my while loop will stop.

Final list

linked list values: 3, 2, 9, 6, 4

9 is the partitioning element.

Note: This question and solution assumes that you are not trying to preserve any ordering except for partition.