86. 分隔链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：

输入：head = [2,1], x = 2
输出：[1,2]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return head;
        }
        ListNode less = new ListNode(), lessTail = less;
        ListNode more = new ListNode(), moreTail = more;

        ListNode cur = head, next;
        while (cur != null) {
            next = cur.next;
            if (cur.val < x) {
                lessTail.next = cur;
                lessTail = cur;
            } else {
                moreTail.next = cur;
                moreTail = cur;
            }
            cur.next = null;
            cur = next;
        }
        ListNode newHead = new ListNode(), newTail = newHead;
        if (less.next != null) {
            newTail.next = less.next;
            newTail = lessTail;
        }

        if (more.next != null) {
            newTail.next = more.next;
            newTail = moreTail;
        }
        return newHead.next;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}