# 分隔链表
给你一个链表的头节点 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
以下错误的选项是？
## aop
### before
```c
#include
using namespace std;
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
```
### after
```c
```
## 答案
```c
class Solution
{
public:
ListNode *partition(ListNode *head, int x)
{
if (!head || !head->next)
return head;
ListNode *p = head;
ListNode *q = head;
ListNode *qq = q;
int flag = 0;
while (q && q->val < x)
{
flag = 1;
p = q;
q = q->next;
}
while (q)
{
if (flag == 0 && q->val < x)
{
qq->next = q->next;
q->next = p;
p = q;
head = p;
q = qq->next;
flag = 1;
}
else if (flag == 1 && q->val < x)
{
qq->next = q->next;
q->next = p->next;
p->next = q;
p = p->next;
q = qq->next;
}
}
return head;
}
};
```
## 选项
### A
```c
class Solution
{
public:
ListNode *partition(ListNode *head, int x)
{
ListNode *dummy = new ListNode(-1);
dummy->next = head;
ListNode *pre = dummy, *cur;
while (pre->next && pre->next->val < x)
pre = pre->next;
cur = pre;
while (cur->next)
{
if (cur->next->val < x)
{
ListNode *tmp = cur->next;
cur->next = tmp->next;
tmp->next = pre->next;
pre->next = tmp;
pre = pre->next;
}
else
{
cur = cur->next;
}
}
return dummy->next;
}
};
```
### B
```c
class Solution
{
public:
ListNode *partition(ListNode *head, int x)
{
ListNode *lessNode = new ListNode(-1);
ListNode *moreNode = new ListNode(-1);
ListNode *l = lessNode;
ListNode *m = moreNode;
while (head)
{
if (head->val >= x)
{
m->next = head;
m = m->next;
}
else
{
l->next = head;
l = l->next;
}
head = head->next;
}
l->next = moreNode->next;
m->next = NULL;
return lessNode->next;
}
};
```
### C
```c
class Solution
{
public:
ListNode *partition(ListNode *head, int x)
{
if (head == NULL || head->next == NULL)
return head;
ListNode *ahead, *p, *after, *p1;
p = head;
while (p && p->val < x)
{
ahead = p;
p = p->next;
}
if (p == head)
ahead = p;
if (p)
after = p->next;
p1 = p;
while (after)
{
if (after->val < x)
{
if (p == head)
{
head = after;
ahead = head;
}
else
{
ahead->next = after;
ahead = after;
}
p1->next = after->next;
}
else
{
p1 = after;
}
after = after->next;
}
if (ahead != p)
ahead->next = p;
return head;
}
};
```