solution.md

# 反转链表 II

给你单链表的头指针 <code>head</code> 和两个整数 <code>left</code> 和 <code>right</code> ，其中 <code>left <= right</code> 。请你反转从位置 <code>left</code> 到位置 <code>right</code> 的链表节点，返回 <strong>反转后的链表</strong> 。<p><strong>示例 1：</strong></p><img alt="" src="https://img-blog.csdnimg.cn/img_convert/c664df96e99b9097662307d2e0368322.png#pic_center" /><pre><strong>输入：</strong>head = [1,2,3,4,5], left = 2, right = 4<strong><br />输出：</strong>[1,4,3,2,5]</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>head = [5], left = 1, right = 1<strong><br />输出：</strong>[5]</pre><p><strong>提示：</strong></p><ul>	<li>链表中节点数目为 <code>n</code></li>	<li><code>1 <= n <= 500</code></li>	<li><code>-500 <= Node.val <= 500</code></li>	<li><code>1 <= left <= right <= n</code></li></ul><p><strong>进阶：</strong> 你可以使用一趟扫描完成反转吗？</p>
<p>以下<span style="color:red">错误</span>的选项是？</p>

## aop

### before

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

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

### after

```c

```

## 答案

```c
class Solution
{
public:
    ListNode *reverseBetween(ListNode *head, int m, int n)
    {
        ListNode *dummy = new ListNode(-1), *pre = dummy;
        dummy->next = head;
        for (int i = 0; i < m; ++i)
            pre = pre->next;
        ListNode *cur = pre->next;
        for (int i = m; i < n - 1; ++i)
        {
            ListNode *t = cur->next;
            cur->next = t->next;
            t->next = pre->next;
            pre->next = t;
        }
        return dummy->next;
    }
};
```
## 选项


### A

```c
class Solution
{
public:
    ListNode *reverseBetween(ListNode *head, int m, int n)
    {
        if (head == nullptr || head->next == nullptr || m == n)
            return head;
        ListNode *pre = nullptr, *cur = head;
        while (m > 1)
        {
            pre = cur;
            cur = cur->next;
            m--;
            n--;
        }
        ListNode *tail = cur, *con = pre;
        ListNode *third;
        while (n > 0)
        {
            third = cur->next;
            cur->next = pre;
            pre = cur;
            cur = third;
            n--;
        }
        if (con)
        {
            con->next = pre;
        }
        else
        {
            head = pre;
        }

        tail->next = cur;
        return head;
    }
};
```

### B

```c
class Solution
{
public:
    ListNode *reverseBetween(ListNode *head, int m, int n)
    {
        if (head == NULL || m == n)
            return head;
        ListNode *pm = head, *pn = head;
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *pm0 = dummy;
        while (m-- > 1)
            pm = pm->next, pm0 = pm0->next;
        while (n-- > 1)
            pn = pn->next;

        ListNode *pPre = pm, *pCur = pPre->next, *pn2 = pn->next;

        while (pCur != pn2)
        {
            if (pCur)
            {
                ListNode *pNext = pCur->next;
                pCur->next = pPre;
                pPre = pCur;
                pCur = pNext;
            }
        }
        pm0->next = pn;
        pm->next = pn2;

        return dummy->next;
    }
};
```

### C

```c
class Solution
{
public:
    ListNode *reverseBetween(ListNode *head, int m, int n)
    {
        if ((head == NULL) || (head->next == NULL))
            return head;
        ListNode *first = new ListNode(0);
        first->next = head;
        int cnt = 1;
        for (int i = 0; i < m - 1; ++i)
        {
            first = first->next;
            cnt++;
        }
        ListNode *old_pre = first;
        ListNode *cur = first->next;
        ListNode *cur_next = cur->next;
        ListNode *new_pre = cur;
        ListNode *temp;
        /*反转*/
        while ((cur != NULL) && (cnt < n))
        {
            temp = cur_next->next;
            cur_next->next = cur;
            cur = cur_next;
            cur_next = temp;
            cnt++;
        }

        old_pre->next = cur;
        new_pre->next = cur_next;
        if (m == 1)
            return cur;
        else
            return head;
    }
};
```