# 0086. 分隔链表
### 题目地址(86. 分隔链表)
### 题目描述
```
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
```
### 前置知识
* 链表
### 公司
* 阿里
* 腾讯
* 百度
* 字节
### 思路
* 设定两个虚拟节点，dummyHead1 用来保存小于该值的链表，dummyHead2 来保存大于等于该值的链表
* 遍历整个原始链表，将小于该值的放于 dummyHead1 中，其余的放置在 dummyHead2 中
遍历结束后，将 dummyHead2 插入到 dummyHead1 后面
(图片来自： )
### 关键点解析
* 链表的基本操作（遍历）
* 虚拟节点 dummy 简化操作
* 遍历完成之后记得`currentL1.next = null;`否则会内存溢出
> 如果单纯的遍历是不需要上面操作的，但是我们的遍历会导致 currentL1.next 和 currentL2.next 中有且仅有一个不是 null， 如果不这么操作的话会导致两个链表成环，造成溢出。
### 代码
* 语言支持: Javascript，Python3, CPP
```js
/**
* @param {ListNode} head
* @param {number} x
* @return {ListNode}
*/
var partition = function (head, x) {
const dummyHead1 = {
next: null,
};
const dummyHead2 = {
next: null,
};
let current = {
next: head,
};
let currentL1 = dummyHead1;
let currentL2 = dummyHead2;
while (current.next) {
current = current.next;
if (current.val < x) {
currentL1.next = current;
currentL1 = current;
} else {
currentL2.next = current;
currentL2 = current;
}
}
currentL2.next = null;
currentL1.next = dummyHead2.next;
return dummyHead1.next;
};
```
Python3 Code:
```python
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
"""在原链表操作，思路基本一致，只是通过指针进行区分而已"""
# 在链表最前面设定一个初始node作为锚点，方便返回最后的结果
first_node = ListNode(0)
first_node.next = head
# 设计三个指针，一个指向小于x的最后一个节点，即前后分离点
# 一个指向当前遍历节点的前一个节点
# 一个指向当前遍历的节点
sep_node = first_node
pre_node = first_node
current_node = head
while current_node is not None:
if current_node.val < x:
# 注意有可能出现前一个节点就是分离节点的情况
if pre_node is sep_node:
pre_node = current_node
sep_node = current_node
current_node = current_node.next
else:
# 这段次序比较烧脑
pre_node.next = current_node.next
current_node.next = sep_node.next
sep_node.next = current_node
sep_node = current_node
current_node = pre_node.next
else:
pre_node = current_node
current_node = pre_node.next
return first_node.next
```
CPP Code:
```cpp
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode dummy, geHead, *ltTail = &dummy, *geTail = &geHead;
while (head) {
auto p = head;
head = head->next;
if (p->val < x) {
ltTail->next = p;
ltTail = p;
} else {
geTail->next = p;
geTail = p;
}
}
ltTail->next = geHead.next;
geTail->next = NULL;
return dummy.next;
}
};
```
**复杂度分析**
* 时间复杂度：$O(N)$
* 空间复杂度：$O(1)$
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/86.partition-list.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.