LeetCode中等难度的链表题——86. 分隔链表，这道题核心考察链表的遍历与拼接，看似简单但藏着容易踩坑的细节，尤其适合刚入门链表操作的小伙伴练手，吃透它能帮你加深对链表指针移动的理解。

一、题目解读：看清要求，避免踩坑

先明确题目核心需求，避免做无用功：

• 给定一个链表的头节点head和一个特定值x，需要将链表分隔成两部分

• 规则1：所有小于x的节点，都要出现在大于或等于x的节点之前

• 规则2：必须保留两个分区中每个节点的初始相对位置（这是关键，不能打乱原有的顺序）

举个直观例子帮助理解：

输入：head = [1,4,3,2,5,2], x = 3

输出：[1,2,2,4,3,5]

解析：小于3的节点是1、2、2（保持原有顺序），大于等于3的是4、3、5（也保持原有顺序），拼接后就是最终结果。

二、解题思路：虚拟头节点是关键

链表题的很多难点，都可以用「虚拟头节点」来简化——它能避免处理头节点为空的边界情况，让指针移动更顺畅。这道题的核心思路就是「分治+拼接」，步骤如下：

1. 拆分思路：用两个链表分别存储两类节点

我们创建两个虚拟头节点，分别对应「小于x的链表」和「大于等于x的链表」：

• lessHead：小于x的链表的虚拟头节点，lessTail是它的尾指针（用于拼接新节点）

• greaterHead：大于等于x的链表的虚拟头节点，greaterTail是它的尾指针

2. 遍历原链表，分配节点

用curr指针遍历原链表，逐个判断每个节点的值：

• 如果curr.val < x：将curr节点拼接到lessTail后面，然后lessTail向后移动一步

• 否则：将curr节点拼接到greaterTail后面，然后greaterTail向后移动一步

• 每次判断后，curr指针继续向后移动（curr = curr.next），直到遍历完所有节点

3. 拼接两个链表，处理边界

遍历结束后，需要将两个链表连接起来：

• 将lessTail的next指向greaterHead的next（跳过greater的虚拟头节点，连接真实的第一个节点）

• 关键细节：将greaterTail的next设为null！否则可能导致链表成环（原链表的最后一个节点可能指向前面的节点）

4. 返回结果

最终结果是lessHead的next（跳过less的虚拟头节点，返回真实的头节点）。

三、代码逐行解析：看懂每一步的意义

给出的代码是TypeScript版本（适配LeetCode的链表定义），我们逐行拆解，新手也能看懂：

function partition(head: ListNode | null, x: number): ListNode | null {
  // 1. 创建两个虚拟头节点，分别管理两类节点
  let lessHead = new ListNode(0);
  let lessTail = lessHead; // less链表的尾指针，初始指向虚拟头
  let greaterHead = new ListNode(0);
  let greaterTail = greaterHead; // greater链表的尾指针，初始指向虚拟头
  
  // 2. curr指针遍历原链表，初始指向头节点
  let curr = head;
  
  // 3. 循环遍历所有节点
  while (curr) {
    if (curr.val < x) {
      // 小于x，拼接到less链表
      lessTail.next = curr;
      lessTail = lessTail.next; // 尾指针后移
    } else {
      // 大于等于x，拼接到greater链表
      greaterTail.next = curr;
      greaterTail = greaterTail.next; // 尾指针后移
    }
    curr = curr.next; // 遍历下一个节点
  }
  
  // 4. 拼接两个链表，处理环的问题
  lessTail.next = greaterHead.next; // 连接less尾部和greater的真实头部
  greaterTail.next = null; // 切断greater尾部的多余连接，防止成环
  
  // 5. 返回结果（跳过less的虚拟头节点）
  return lessHead.next;
};

四、关键注意事项（避坑重点）

这道题看似简单，但新手很容易踩以下2个坑，一定要注意：

坑1：忘记设置greaterTail.next = null，导致链表成环

原链表的最后一个节点（假设属于greater链表），它的next可能指向一个小于x的节点（已经被分配到less链表）。如果不将greaterTail.next设为null，拼接后就会形成环，遍历链表时会陷入死循环。

坑2：打乱节点的初始相对位置

题目要求「保留初始相对位置」，所以我们不能用排序的思路，只能「顺序遍历、顺序拼接」——无论less还是greater链表，都是按原链表的顺序添加节点，这样才能保证相对位置不变。

五、复杂度分析：高效且简洁

这道解法的效率很高，完全贴合LeetCode的最优解要求：

• 时间复杂度：O(n)，n是链表的长度，我们只遍历了一次链表，每个节点只处理一次

• 空间复杂度：O(1)，我们只创建了4个指针（lessHead、lessTail、greaterHead、greaterTail）和2个虚拟节点，没有使用额外的存储空间（链表节点是原有的，只是重新拼接）

六、总结：链表操作的核心技巧

通过这道题，我们可以总结出链表操作的2个核心技巧，适用于很多同类题目：

1. 虚拟头节点：解决头节点为空的边界问题，让指针移动更统一、更简洁

2. 分治思想：将复杂问题拆分成简单的子问题（本题拆成两个小链表），处理完后再拼接，降低解题难度

其实这道题的本质，就是「链表的拆分与重组」，吃透它之后，再做类似的链表分区、拼接题目，都会轻松很多。