面试题 02.04. 分割链表

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

你不需要 保留 每个分区中各节点的初始相对位置。

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

class Solution {
    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return null;
        }
        ListNode h1 = new ListNode(0), t1 = h1;
        ListNode h2 = new ListNode(0), t2 = h2;
        ListNode h3 = new ListNode(0), t3 = h3;

        ListNode cur = head, next;
        while (cur != null) {
            next = cur.next;
            if (cur.val < x) {
                t1.next = cur;
                t1 = cur;
            } else if (cur.val == x) {
                t2.next = cur;
                t2 = cur;
            } else {
                t3.next = cur;
                t3 = cur;
            }
            cur.next = null;
            cur = next;
        }

        ListNode h = new ListNode(0), t = h;

        if (h1 != t1) {
            t.next = h1.next;
            t = t1;
        }

        if (h2 != t2) {
            t.next = h2.next;
            t = t2;
        }

        if (h3 != t3) {
            t.next = h3.next;
            t = t3;
        }

        return h.next;
    }
}


class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}