// @Title: 分隔链表 (Partition List)
// @Author: qisiii
// @Date: 2024-09-25 16:27:26
// @Runtime: 0 ms
// @Memory: 40.9 MB
// @comment: 
// @flag: 
/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode min = new ListNode(-1), result = min;
        ListNode max = new ListNode(-1), temp = max;
        while (head != null) {
            if (head.val >= x) {
                max.next = head;
                max = max.next;
            } else {
                min.next = head;
                min = min.next;
            }
            head = head.next;
        }
        max.next = null;
        min.next = temp.next;
        return result.next;
    }
}