按值分割链表

dummy头结点

本题使用含有dummy头的两个链表，分别储存小于x和大于等于x的节点，最后再合并两个节点即可。

/**
 * 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) {
        ListNode dummySmall = new ListNode(-1);
        ListNode dummyLarge = new ListNode(-1);
        dummyLarge.next = head;
        dummySmall.next = head;
        ListNode pSmall = dummySmall, pLarge = dummyLarge;
        while (head != null) {
            if (head.val < x) {
                pSmall.next = head;
                pSmall = pSmall.next;
            } else {
                pLarge.next = head;
                pLarge = pLarge.next;
            }
            head = head.next;
        }
        pLarge.next = null;
        pSmall.next = null;
        ListNode dummyRes = mergeList(dummySmall, dummyLarge);
        return dummyRes.next;
    }

    // 合并左链表和右链表，l1在前，l2在后
    public static ListNode mergeList(ListNode l1, ListNode l2) {
        ListNode p = l1;
        while (p.next != null) {
            p = p.next;
        }
        // 大链表l2开头是前面new的一个值为-1的节点，连接两个dummy链表，
        // 只保留前面l1的dummy头，l2的dummy头不要，所以连接l2.next
        p.next = l2.next;
        return l1;
    }
}