86. 分隔链表

✨核心逻辑

本题采用 双哑链表（双虚拟头节点 + 尾指针） 的策略：

建立两个独立链表：创建两个虚拟头节点 small 和 large，分别用于存放原链表中值 小于 x 和 大于等于 x 的所有节点。
尾插法保持相对顺序：各自使用一个尾指针 smallTail 和 largeTail 指向链表的末尾，遍历原链表时直接通过尾指针将当前节点追加到对应链表的末尾，保证节点在两个分区内的初始相对位置保持不变。
原链表遍历：使用 cur 指针从左到右扫描原链表，根据节点的值判断归属，将其接入对应的新链表。
拼接与收尾：扫描结束后，将 large 链表的尾部置为 null（防止形成环），再将 small 链表的尾部指向 large 链表的头部（large.next）。最后返回 small.next 即可。

🔥代码实现（含详细变量注释）

class Solution {
    public ListNode partition(ListNode head, int x) {
        // small：虚拟头节点，指向所有值小于 x 的节点组成的新链表的头
        ListNode small = new ListNode(0);
        // large：虚拟头节点，指向所有值大于等于 x 的节点组成的新链表的头
        ListNode large = new ListNode(0);
        
        // smallTail：小链表的尾指针，始终指向 small 链表的最后一个节点
        ListNode smallTail = small;
        // largeTail：大链表的尾指针，始终指向 large 链表的最后一个节点
        ListNode largeTail = large;
        
        // cur：原链表的遍历指针，用于逐个扫描节点，判断归属
        ListNode cur = head;
        
        // 遍历原链表，直到所有节点都被扫描过
        while (cur != null) {
            // 如果当前节点的值小于 x，将其追加到 small 链表的尾部
            if (cur.val < x) {
                smallTail.next = cur;
                smallTail = smallTail.next; // 更新 small 链表的尾指针
            } else {
                // 如果当前节点的值大于等于 x，将其追加到 large 链表的尾部
                largeTail.next = cur;
                largeTail = largeTail.next; // 更新 large 链表的尾指针
            }
            // 将原链表指针向后移动一位，继续判断下一个节点
            cur = cur.next;
        }
        
        // 关键步骤：将 large 链表的尾部置为 null，切断它与原链表后续节点的连接，防止产生环
        largeTail.next = null;
        // 将 small 链表的尾部与 large 链表的真实头节点（跳过虚拟头节点 large）拼接在一起
        smallTail.next = large.next;
        
        // 返回 small 链表的真实头节点（跳过虚拟头节点 small），即为分隔后的结果链表
        return small.next;
    }
}

⏱️复杂度分析
- 时间复杂度：O(N)，其中 N 是链表的长度。我们只需要遍历一次原链表，在遍历过程中进行常数次的节点指针操作。
- 空间复杂度：O(1)，仅使用了 small、large、smallTail、largeTail、cur 五个额外的指针变量，没有创建新的节点，只是原地重组了链表的连接关系。