leetcode 86. 分隔链表

题目描述

给定一个链表和一个特定值 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;
    }
}