86. 分隔链表

题目链接：86. 分隔链表

题目描述

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

你应当 保留 两个分区中每个节点的初始相对位置。

核心思考：双虚拟头节点构建法

本题最直观的解法是模拟法。
与其在原来的链表上进行复杂的节点移除和插入操作，不如直接建立两条全新的链表：

1. 小链表 (dummy1)：专门用来接收所有值 < x 的节点。
2. 大链表 (dummy2)：专门用来接收所有值 >= x 的节点。

我们只需遍历原链表，遇到小于 x 的节点将其链接到 dummy1 后，大于等于 x 的节点将其链接到 dummy2 后。遍历结束后，再将 dummy1 的尾部连接到 dummy2 的实际头部（即 dummy2.next），即可完成链表的分隔。

细节：处理链表成环（断尾）

在将原链表节点重组到新链表时，一个常见的错误是链表成环。这是因为节点挂载到新链表时，依然保留着原始的 next 指针。如果不加以处理，新链表的尾节点可能会指向链表中的某个前驱节点，从而导致结构成环。

解决这个问题，有两种常见的处理思路（代码中均有注释说明）：

• 法 1：逐个断开 next 指针
  在将当前节点 curp 接入新链表之前，先利用临时变量将其下游 curp.next 暂存，随后立刻将 curp.next 置为 None。这样可以保证接入新链表的每个节点都是独立的，从根本上阻断了成环的可能。
• 法 2：遍历结束后统一断开结尾
  在挂载节点的过程（如 p1.next = curp）中，大部分节点的 next 指针已经被重新指向了正确的下一个节点。因此在遍历中，我们可以直接推进 curp = curp.next，无需刻意断开原指针。然而，当遍历结束时，大链表的尾节点 p2 的 next 指针依旧保留着原始状态。如果它恰好指向了一个被分配至小链表中的节点，拼接两链表后便会成环。
  因此，使用法 2 的核心在于：在退出循环后、拼接大小链表之前，必须显式地执行一次 p2.next = None，强制断开尾节点的旧指针。 这种做法相较于法 1 更加简洁，也是在算法实现中更为标准的推荐写法。

解题思路 (Python)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        dummy1 = ListNode()
        dummy2 = ListNode()
        p1,p2 = dummy1,dummy2

        curp = head

        while curp:
            if curp.val < x:
                p1.next = curp
                p1 = p1.next
            else:
                p2.next = curp
                p2 = p2.next

            # 法1：清除目前curp.next指针的指向（因为在指向老的两个链表之一）
            # temp = curp.next
            # curp.next = None
            # curp = temp

            # 法2：最后连接前清除p2的尾巴
            curp = curp.next
        p2.next = None

        p1.next = dummy2.next # 比x小的和比x大的连起来

        return dummy1.next

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是原链表的长度。我们仅仅对原链表进行了一次线性无回溯的遍历。
• 空间复杂度：$O(1)$。虽然我们“建立”了两条新链表，但实际上只是额外声名了几个虚拟节点 (dummy1, dummy2, p1, p2) 的指针变量，那些庞大的节点内存全部都是原地复用的原链表节点对象，并没有申请 $O(n)$ 的新内存。