.
2020-01-15 吴亲库里 库里的深夜食堂
给定一个链表和一个特定的值。让我们分割链表，使得所有小于给定值 (即这里的x) 的节点都位于大于或者等于 x 之前。题目要求我们保留节点的初始相对位置。
这个问题的解决关键就在于 改变后的链表有一个规律，即在某个点上，必然存在该点之前的元素都小于 x，该点之后的数都大于等于x。也就是说我们可以设置初始化两个链表，然后遍历原链表，把小于x 的节点放置到其中一个链表(beforeNode)，大于等于 x 的放置到另一个链表(afterNode),这样的话最后我们只要把这两个链表连接起来即可。因为我们遍历原链表是从头到尾的，所以也不会去改变他们的相对位置。
/**
* 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) {
$beforeNode=new ListNode(-1);
$afterNode=new ListNode(-1);
$before=$beforeNode;
$after=$afterNode;
while($head !=null){
if($head->val<$x){
$before->next=$head;
$before=$before->next;
}else{
$after->next=$head;
$after=$after->next;
}
$head=$head->next;
}
$after->next=null;
$before->next=$afterNode->next;
return $beforeNode->next;
}
}