0086.分隔链表

题目链接

https://leetcode.cn/problems/partition-list/

题目描述

给定单链表 head 和整数 x，将链表分成两部分：所有小于 x 的节点在前，其余节点在后，并保持各自原有的相对顺序，返回分区后的链表。

解题思路

• 双虚拟头分链再拼接：
  • 使用两个虚拟头 minDummy、maxDummy 分别串起小于 x 与大于等于 x 的节点。
  • 单次遍历按值分发到对应链表尾部。
  • 最后将小链尾接到大链头，且将大链尾的 next 置为 null，避免成环。
• 边界情况：
  • 原链为空直接返回空。
  • 所有节点均小于 x 或均不小于 x 时，拼接逻辑同样正确。

题解代码

classSolution{publicListNodepartition(ListNodehead,intx){ListNodeminDummy=newListNode(0),maxDummy=newListNode(0);ListNodemin=minDummy,max=maxDummy;while(head!=null){if(head.val<x){min.next=head;min=min.next;}else{max.next=head;max=max.next;}head=head.next;}// 拼接与收尾min.next=maxDummy.next;max.next=null;returnminDummy.next;}}

复杂度分析

• 时间复杂度：O(n)，单次遍历。
• 空间复杂度：O(1)，仅使用常数级额外指针。