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
}