题目描述
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
示例 2：
提示：
- 链表中节点的数目在范围 [0, 200] 内
- -100 <= Node.val <= 100
- -200 <= x <= 200
题目解析
双指针思路，p1指向小于x的节点，p2指向不小于x的节点，最后 p1 链表和 p2 链表连接。
参考代码
以下为 Java 代码。
复杂度分析
- 时间复杂度: O(n)，其中 nnn 是原链表的长度。我们对该链表进行了一次遍历。
- 空间复杂度: O(1)。
