leetcode：92. 反转链表 II

题目

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
进阶：你可以使用一趟扫描完成反转吗？

示例 1：
[中等] 92. 反转链表 II - 图1

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

解答 & 代码

解法一：一趟遍历

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if(head == nullptr || head->next == nullptr)
            return head;

        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* beforeReverse = nullptr;    // 待反转部分之前的一个节点
        ListNode* reverseLast = nullptr;    // 待反转部分反转后的最后一个节点（即待反转部分的第一个节点）
        ListNode* reverseFirst = nullptr;    // 待反转部分反转后的第一个节点（即待反转部分的最后一个节点）
        int cnt = 0;                        // 记录当前遍历到第 cnt 个节点
        // 遍历链表（遍历到 right 之前即可）
        while(cur != nullptr && cnt < right)
        {
            ++cnt;
            // 如果当前是待反转部分之前，正常右移即可
            if(cnt < left)
            {
                // 如果当前节点是第 left-1 个，记为 beforeReverse
                if(cnt == left - 1)
                    beforeReverse = cur;
                // 右移
                pre = cur;
                cur = cur->next;
            }
            // 如果当前遍历到待反转部分
            else if(cnt >= left && cnt <= right)
            {
                // 分别用 reverseLast、reverseFirst 标记第 left、right 个节点
                if(cnt == left)
                    reverseLast = cur;
                if(cnt == right)
                    reverseFirst = cur;
                // 反转链表
                ListNode* next = cur->next;
                cur->next = pre;
                pre = cur;
                cur = next;
            }
        }
        // 将待反转部分反转后的最后一个节点指向第 right+1 个节点
        reverseLast->next = cur;
        // 如果是从头结点开始反转，那么反转部分反转的第一个节点就成为整个链表i虚拟的头节点，返回
        if(left == 1)
            return reverseFirst;
        // 否则
        else
        {
            beforeReverse->next = reverseFirst;    // 将第 left-1 个节点的 next 指向待反转部分反转后的第一个节点
            return head;    // 返回链表头节点
        }
    }
};

复杂度分析：设链表长度为 N

时间复杂度 O(N)
空间复杂度 O(1)

执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 48.15% 的用户
内存消耗：7.2 MB, 在所有 C++ 提交中击败了 88.14% 的用户

解法二：一趟遍历(头插法 + dummyHead)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* dummyHead = new ListNode(-1, head);    // 虚拟头节点
        // 1. 将 pre 节点定位到第 left - 1 个节点
        ListNode* pre = dummyHead;
        for(int i = 0; i < left - 1; ++i)
            pre = pre->next;

        // 2. 头插法反转第 left 至 第 right 个节点
        // cur 节点固定指向原链表第 left 个节点
        ListNode* cur = pre->next;
        for(int i = 0; i < right - left; ++i)
        {
            ListNode* next = cur->next;    // 定位到下一个待反转的节点 next
            cur->next = next->next;        // ① 删除 next 节点
            // 将 next 节点插入到 pre 节点之后（即插入到第 left 个节点的位置上）
            next->next = pre->next;        // ②
            pre->next = next;            // ③
        }

        return dummyHead->next;
    }
};

复杂度分析：设链表长度为 N

时间复杂度 O(N)
空间复杂度 O(1)

执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 48.15% 的用户
内存消耗：7.3 MB, 在所有 C++ 提交中击败了 41.11% 的用户

解法三：递归

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
private:
    ListNode* successor = nullptr;  // 后继节点（第 N + 1 个节点）
    // 递归函数定义：将链表 head 的前 N 个节点反转，并返回反转后的头节点
    ListNode* reverseFirsrtN(ListNode* head, int N)
    {
        // 递归结束条件
        if(N == 0 || N == 1)
        {
            successor = head->next;    // 记录第 N + 1 个节点
            return head;
        }

        // 递归反转以 head->next 为头结点的前 N - 1 个节点，并返回反转后的头节点，记为 last
        ListNode* last = reverseFirsrtN(head->next, N - 1);

        // 将当前节点 head 接到 last 链表的尾部
        head->next->next = head;
        // 当前节点 head 是反转后的第 N 个节点，因此需要将 head->next 接上第 N + 1 个节点
        head->next = successor;
        // 返回 head 链表反转前 N 个节点后的链表头节点
        return last;
    }
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        // 递归结束条件：如果 left == 1，就相当于反转 head 链表的前 right 个元素
        if(left == 1)
            return reverseFirsrtN(head, right);

        // left != 1 说明当前 head 节点不需要反转，递归去处理后续节点直到触发递归结束条件
        head->next = reverseBetween(head->next, left - 1, right - 1);
        // 返回头节点
        return head;
    }
};

复杂度分析：设链表长度为 N

时间复杂度 O(N)
空间复杂度 O(N)：递归栈空间复杂度

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：7.2 MB, 在所有 C++ 提交中击败了 74.93% 的用户