1. 概述

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3

输出: 1->2->2->4->3->5

2. 解题

<?php
class ListNode
{
    public $val = 0;
    /** @var ListNode */
    public $next = null;
    function __construct($val)
    {
        $this->val = $val;
    }
}
class Solution
{
    /**
     * 1->4->3->2->5->2
     * @param ListNode $head
     * @param Integer $x
     * @return ListNode
     */
    public function partition($head, $x)
    {
        $dummy = new ListNode(0);
        $dummy->next = $head;
        $smallErgodic = $bigErgodic =  $dummy;
        $small = $big = null;
        $smallIndex = $bigIndex = 0;
        $j = $i = 0;
        /** @var ListNode $smallHome 小于$x的数应该插入的位置节点 */
        $smallHome = null;
        while (1) {
            // 取出小于$x的节点
            while ($smallErgodic->next && !$small) {
                if ($smallErgodic->next->val < $x) {
                    $small = $smallErgodic->next;
                    $smallIndex = $i;
                }
                $smallErgodic = $smallErgodic->next;
                $i++;
            }
            // 取出大于$x的节点
            while ($bigErgodic->next && !$big) {
                if ($bigErgodic->next->val >= $x) {
                    $big = $bigErgodic->next;
                    $bigIndex = $j;
                }
                $bigErgodic = $bigErgodic->next;
                $j++;
            }
            // 如果已经没有符合条件的情况，这跳出程序
            if (!$small || !$big) {
                break;
            }
            if ($smallIndex < $bigIndex) {
                $smallHome = $small;
            } else {
                // 小的数前移
                $tmp = $smallHome->next;
                $smallHome->next = new ListNode($small->val);
                $smallHome->next->next = $tmp;
                // 删除小的数
                $big->next = $big->next->next;
            }
            $smallIndex = $bigIndex = 0;
            $small = $big = null;
        }
        return $dummy->next;
    }
}
$head = new ListNode(1);
$head->next = new ListNode(4);
$head->next->next = new ListNode(3);
$head->next->next->next = new ListNode(2);
$head->next->next->next->next = new ListNode(5);
$head->next->next->next->next->next = new ListNode(2);
$x = 3;
$cls = new Solution();
$ret = $cls->partition($head, $x);
print_r($ret);