## Description

Partition List

Given 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.

Example:

``````Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
``````

## Solution

 `````` 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 `````` ``````func partition(head *ListNode, x int) *ListNode { // use a new linked list to save 'bigger nodes' bigger := &ListNode{} biggerTail := bigger // this linked list to save 'smaller nodes' slow := &ListNode{ Next: head, } head = slow fast := slow.Next for fast != nil { if fast.Val < x { // slow go to fast(go to slow.next) slow = fast } else { // skip fast, go fast.Next(got slow.next.next) slow.Next = fast.Next // break after fast fast.Next = nil // append fast to bigger linked list biggerTail.Next = fast biggerTail = biggerTail.Next } fast = slow.Next } // concat the two linked lists slow.Next = bigger.Next return head.Next } ``````