# Partition

Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x. If x is contained within the list, the values of x only need to be after the elements less than x (see below). The partition element x can appear anywhere in the "right partition"; it does not need to appear between the left and right partitions.

```
// input: 3 - 5 - 8 - 5 -10 - 2 - 1 [Partition = 5]
// output: 3 - 1 - 2 - 10 - 5 - 5 - 8
```

## Link here to the repo to solve the problem

👉## 👌 Tips

There are many solutions to this problem, most of which are equally optimal in runtime. Some have shorter, cleaner code than others. Can you brainstorm different solutions?

Consider that the elements don't have to stay in the same relative order. We only need to ensure that elements less than the pivot must be before elements greater than the pivot. Does that help you come up with more solutions?

## 👊 Solution 1

This is a pretty straight forward solution, where I have two lists on which I will keep adding the nodes to each depending if the values are smaller or bigger than the pivot. Keeping track of the node which is at the start of each list - as I will have to append them in the end.

Once I've got both lists I just have to iterate over the first list until I get the end and make that node.next the right list.

The runtime of this Algorithm should be O(N) + all the elements that lie in the left-hand side of the pivot.

```
public SingleLinkedListNode partition(int pivot) {
SingleLinkedListNode left = null;
SingleLinkedListNode right = null;
SingleLinkedListNode node = this;
SingleLinkedListNode n = null;
while (node.next != null) {
n = new SingleLinkedListNode(node.data);
if (n.data >= pivot) {
right = appendToStart(right, n);
} else {
left = appendToStart(left, n);
}
node = node.next;
}
// need to also append the last node
n = new SingleLinkedListNode(node.data);
if (node.data >= pivot) {
right = appendToStart(right, n);
} else {
left = appendToStart(left, n);
}
// need to iterate through the left list in order to append the right one to the last element
node = left;
while (node.next != null) {
node = node.next;
}
node.next = right;
return left;
}
private SingleLinkedListNode appendToStart(SingleLinkedListNode list, SingleLinkedListNode newNode) {
if (list == null) list = newNode;
else {
newNode.next = list;
list = newNode;
}
return list;
}
```

## 👊 Solution 2

If it bugs you to keep around four different variables for tracking two linked lists, you're not alone. We can make this code a bit shorter.

If we don't care about making the elements of the list "stable"(which there's no obligation to, since the interviewer hasn't specified that), then we can instead rearrange the elements by growing the list at the head and tail.

In this approach, we start a "new"list (using the existing nodes). Elements bigger than the pivot element are put at the tail and elements smaller are put at the head. Each time we insert an element, we update either the head or tail.

```
public static SingleLinkedListNode partitionSimple(SingleLinkedListNode node, int x) {
SingleLinkedListNode head = node;
SingleLinkedListNode tail = node;
while (node.next != null) {
SingleLinkedListNode next = node.next;
// insert node at head
if (node.data < x) {
node.next = head;
head = node;
// insert node at tail
} else {
tail.next = node;
tail = node;
}
node = node.next;
}
tail.next = null;
return head;
}
```

There are many equally optimal solutions to this problem. If you came up with a different one, that's okay!

*Question borrowed from “Cracking the coding interview”*