  # LeetCode - Partition List

### Problem statement

Given the `head` of a linked list and a value `x`, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Problem statement taken from: https://leetcode.com/problems/partition-list

Example 1: ``````Input: head = [1, 4, 3, 2, 5, 2], x = 3
Output: [1, 2, 2, 4, 3, 5]
``````

Example 2:

``````Input: head = [2, 1], x = 2
Output: [1, 2]
``````

Constraints:

``````- The number of nodes in the list is in the range [0, 200].
- -100 <= Node.val <= 100
- -200 <= x <= 200
``````

### Explanation

#### One pass solution

We can solve the problem in a single iteration using two linked lists. Let's jump to the algorithm directly how it works.

``````- if head == null || head->next == null

- set smallElements, largeElements = new ListNode()

- set smallerIterator, largerIterator = smallElements, largeElements

- smallerIterator = smallerIterator->next
- else
- largerIterator = largerIterator->next
- if end

- while end

- largerIterator->next = null
smallerIterator->next = largeElements->next

- return smallElements->next
``````

The time-complexity of the above approach is O(n), and the space complexity is O(n).

Let's check our algorithm in C++, Golang, and Javascript.

#### C++ solution

``````class Solution {
public:
ListNode* partition(ListNode* head, int x) {
}

ListNode *smallElements = new ListNode();
ListNode *largeElements = new ListNode();

ListNode *smallerIterator = smallElements;
ListNode *largerIterator = largeElements;

smallerIterator = smallerIterator->next;
} else {
largerIterator = largerIterator->next;
}
}

largerIterator->next = NULL;
smallerIterator->next = largeElements->next;

return smallElements->next;
}
};``````

#### Golang solution

``````func partition(head *ListNode, x int) *ListNode {
}

smallElements, largeElements := &ListNode{}, &ListNode{}
smallerIterator, largerIteractor := smallElements, largeElements

smallerIterator = smallerIterator.Next
} else {
largerIteractor = largerIteractor.Next
}
}

largerIteractor.Next = nil
smallerIterator.Next = largeElements.Next

return smallElements.Next
}``````

#### Javascript solution

``````var partition = function(head, x) {
}

let smallElements = new ListNode(0, null);
let largeElements = new ListNode(0, null);

let smallerIterator = smallElements;
let largerIterator = largeElements;

smallerIterator = smallerIterator.next;
} else {
largerIterator = largerIterator.next;
}
}

largerIterator.next = null;
smallerIterator.next = largeElements.next;

return smallElements.next;
};``````

Let's dry-run our algorithm to see how the solution works.

``````Input: head = [1, 4, 3, 2, 5, 2], x = 3

false

Step 2: ListNode *smallElements = new ListNode()
ListNode *largeElements = new ListNode()

ListNode *smallerIterator = smallElements
ListNode *largerIterator = largeElements

1 < 3
true

smallerIterator->next = 1

smallerIterator = smallerIterator->next
= 1

= 4

smallerIterator = 1
largerIterator = nil

4 < 3
false
else

largerIterator->next = 4

largerIterator = largerIterator->next
= 4

= 3

smallerIterator = 1
largerIterator = 4

3 < 3
false
else

largerIterator->next = 3

largerIterator = largerIterator->next
= 3

= 2

smallerIterator = 1
largerIterator = 4 -> 3

2 < 3
true

smallerIterator->next = 2

smallerIterator = smallerIterator->next
= 2

= 5

smallerIterator = 1 -> 2
largerIterator = 4 -> 3

5 < 3
false
else

largerIterator->next = 5

largerIterator = largerIterator->next
= 5

= 2

smallerIterator = 1 -> 2
largerIterator = 4 -> 3 -> 5

2 < 3
true

smallerIterator->next = 2

smallerIterator = smallerIterator->next
= 2

= nil

smallerIterator = 1 -> 2 -> 2
largerIterator = 4 -> 3 -> 5

Step 10: largerIterator->next = nil
4 -> 3 -> 5 -> nil

smallerIterator->next = largeElements->next
= 4 -> 3 -> 5 -> nil

so the complete list is
1 -> 2 -> 2 -> 4 -> 3 -> 5 -> nil

Step 11: return smallElements->next

We return the answer as [1, 2, 2, 4, 3, 5].
``````