gold-2-4

给你一个链表的头节点 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]

提示：

• 链表中节点的数目在范围 [0, 200] 内
• -100 <= Node.val <= 100
• -200 <= x <= 200

//leetcode submit region begin(Prohibit modification and deletion)
/**
 * 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 small = null;
        ListNode big = null;
        ListNode temp = head;
        ListNode firstBig = null;
        ListNode firstSmall = null;

        while (temp != null) {
            if (temp.val < x) {
                if (small == null) {
                    small = temp;
                    firstSmall = temp;
                } else {
                    small.next = temp;
                    small = temp;
                }
            } else {
                if (big == null) {
                    big = temp;
                    firstBig = temp;
                } else {
                    big.next = temp;
                    big = temp;
                }
            }
            temp = temp.next;
        }

        if (small != null) {
            small.next = firstBig;
        }
        if (big != null) {
            big.next = null;
        }

        if (firstSmall != null) {
            return firstSmall;
        } else {
            return firstBig;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)