题目描述

请将链表中第 $n$ 个节点和第 $m$ 个节点之间的部分翻转。
链表最多只能遍历一遍。

注意：$1 \le m \le n \le$ 链表长度。

样例

输入：1->2->3->4->5->NULL, m = 2, n = 4
输出：1->4->3->2->5->NULL

算法

(模拟) $O(n)$

假设初始链表如下所示：

第一步，我们先将 $m$ 到 $n$ 之间的指针翻转（不包含第 $m$ 个节点），如下所示：

第二步我们将 $m$ 的指针指向 $c$，将 $a$ 的指针指向 $n$，如下所示：

此时我们就完成了 $m$ 到 $n$ 之间的翻转！

时间复杂度分析：整个链表只遍历了一遍，所以时间复杂度是 $O(n)$。

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (m == n) return head;
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *p = dummy;
        for (int i = 0; i < m - 1; i ++ )
            p = p->next;
        ListNode *a = p, *b = a->next, *c = b->next;
        for (int i = m + 1; i <= n; i ++ )
        {
            ListNode *d = c->next;
            c->next = b;
            b = c;
            c = d;
        }
        a->next->next = c;
        a->next = b;
        return dummy->next;
    }
};