86. 分隔链表

题意：

解题思路：

思路：(线性扫描) O(n)
1. 定义两个头节点，smallHead, bigHead 分别指向头节点；
2. 遍历链表，对于小于x的则插入small的后面，反之则插入到big的后面；
3. 最后将bigHead链表插入到smallHead后面；

PHP代码实现：

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val) { $this->val = $val; }
 * }
 */
class Solution {
    /**
     * @param ListNode $head
     * @param Integer $x
     * @return ListNode
     */
    function partition($head, $x) {
        return $this->partition1($head, $x);
        $smallHead = new ListNode(0);
        $bigHead = new ListNode(0);
        $small = $smallHead;
        $big = $bigHead;
        while ($head) {
            $temp = new ListNode($head->val);
            if ($head->val < $x) {
                $small->next = $temp;
                $small = $small->next;
            } else {
                $big->next = $temp;
                $big = $big->next;
            }
            $head = $head->next;
        }
        $small->next = $bigHead->next;
        return $smallHead->next;
    }
    // Time: O(n), Space: O(1)
    //分割成一大一小两条链表，最后合并
    function partition1($head, $x) {
        if ($head == null) return;
        $smallHead = new ListNode(0);
        $bigHead = new ListNode(0);
        $small = $smallHead;
        $big = $bigHead;
        for ($p = $head; $p != null; $p = $p->next) {
            if ($p->val < $x) {
                $small->next = $p;
                $small = $small->next;
            } else {
                $big->next = $p;
                $big = $big->next;
            }
        }
        $small->next = $bigHead->next;
        $big->next = null;
        return $smallHead->next;
    }
}

GO代码实现：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func partition(head *ListNode, x int) *ListNode {
    smallHead, bigHead := &ListNode{}, &ListNode{}
    small, big := smallHead, bigHead
    for head != nil {
        temp := &ListNode{head.Val, nil}
        if head.Val < x {
            small.Next = temp
            small = small.Next
        } else {
            big.Next = temp
            big = big.Next
        }
        head = head.Next
    }
    big.Next = nil
    small.Next = bigHead.Next
    return smallHead.Next
}