# 分隔链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2
输出：[1,2]
提示：
- 链表中节点的数目在范围
[0, 200] 内 -100 <= Node.val <= 100-200 <= x <= 200
## template
```cpp
#include
#include
struct ListNode
{
int val;
struct ListNode *next;
};
struct ListNode *partition(struct ListNode *head, int x)
{
struct ListNode dummy;
struct ListNode *prev1 = &dummy, *pivot;
dummy.next = head;
for (pivot = head; pivot != NULL; pivot = pivot->next)
{
if (pivot->val >= x)
{
break;
}
prev1 = pivot;
}
struct ListNode *p = pivot->next;
struct ListNode *prev2 = pivot;
while (p != NULL)
{
if (p->val < x)
{
prev2->next = p->next;
p->next = prev1->next;
prev1->next = p;
prev1 = p;
p = prev2->next;
}
else
{
prev2 = p;
p = p->next;
}
}
return dummy.next;
}
int main(int argc, char **argv)
{
if (argc < 2)
{
fprintf(stderr, "Usage: ./test target n1 n2 n3...\n");
exit(-1);
}
int i, target = atoi(argv[1]);
struct ListNode *head = NULL;
struct ListNode *prev = NULL;
struct ListNode *p;
for (i = 0; i < argc - 2; i++)
{
p = malloc(sizeof(*p));
p->val = atoi(argv[i + 2]);
p->next = NULL;
if (head == NULL)
{
head = p;
prev = head;
}
else
{
prev->next = p;
prev = p;
}
}
p = partition(head, target);
while (p != NULL)
{
printf("%d ", p->val);
p = p->next;
}
printf("\n");
return 0;
}
```
## 答案
```cpp
```
## 选项
### A
```cpp
```
### B
```cpp
```
### C
```cpp
```