solution.md

# 分隔链表

<p>给你一个链表的头节点 <code>head</code> 和一个特定值<em> </em><code>x</code> ，请你对链表进行分隔，使得所有 <strong>小于</strong> <code>x</code> 的节点都出现在 <strong>大于或等于</strong> <code>x</code> 的节点之前。</p><p>你应当 <strong>保留</strong> 两个分区中每个节点的初始相对位置。</p><p> </p><p><strong>示例 1：</strong></p><img alt="" src="https://cdn.jsdelivr.net/gh/doocs/leetcode@main/solution/0000-0099/0086.Partition%20List/images/partition.jpg" style="width: 662px; height: 222px;" /><pre><strong>输入：</strong>head = [1,4,3,2,5,2], x = 3<strong><br />输出</strong>：[1,2,2,4,3,5]</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>head = [2,1], x = 2<strong><br />输出</strong>：[1,2]</pre><p> </p><p><strong>提示：</strong></p><ul>	<li>链表中节点的数目在范围 <code>[0, 200]</code> 内</li>	<li><code>-100 <= Node.val <= 100</code></li>	<li><code>-200 <= x <= 200</code></li></ul>
<p>以下<font color="red">错误</font>的选项是？</p>

## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
```
### after

```cpp

```

## 答案

```cpp
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

```cpp
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

```cpp
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

```cpp
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;
    }
};
```