题目描述
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
相关话题： 链表、双指针 难度： 中等
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
思路：
思路其实和荷兰国旗问题的partition差不多，只是有些边界问题需要注意。
- 定义一个
left指针指向小于x的节点的部分的最后一个节点；p指针遍历链表 - 如果
p.next指向节点的值小于x，那么需要将其脱离并插入到left的后面，left后移一个节点； - 一般地，
p指针不需要动，因为脱离了p.next后，p的下一个节点更新了。然而，有个边界问题是left更新后(left = left.next)，p在left的左边了，其实left左边的节点都是遍历过了的，p应该向前移动。
如上图，节点1插入到left的后面，left后移一位，p应该跟上。 -
p.next = null结束
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
if(head == null) return null;
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
ListNode left = head;
for(ListNode p = head;p.next != null;){
if(p.next.val < x){
ListNode tmp = p.next;
p.next = tmp.next;
tmp.next = left.next;
left.next = tmp;
left = left.next;
p = p.next == left?p.next:p;
}else{
p = p.next;
}
}
return head.next;
}
}
