题解 | #链表内指定区间反转# - O(N)&&O(1)

思路

题目要求翻转指定区间，首先考虑什么情况不翻转：

• head == nullptr：链表空
• head->next = nullptr：链表只有一个元素
• m == n，翻转区间只有 $11$ 个元素

创建一个哑节点 dummy 链接到表前。这样处理如果翻转区间为头就很好处理。

给定 prev = dummy 。遍历链表，将 prev 遍历到翻转区间首节点的前驱结点。

将 head = prev->next ，让 head 指向翻转区间的第一个节点

再遍历链表，在遍历过程中完成区间翻转，步骤：

• 给定变量 tmp ，存放 head->next ，节点 tmp 为当前需要反转头插的节点
• 然后将 head->next = tmp->next ，让 head 指向当前需要翻转头插节点的后驱节点
• 之后让当前需要翻转的节点指向 prev->next ，让当前翻转的节点成为区间的首节点
• 将 prev->next = tmp ，将区间第一个节点的前驱节点链接到第一个节点

最后恢复现场，使 head 重新指向链表头。

销毁哑节点，返回 head 。

代码

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (head == nullptr || head->next == nullptr || m == n) {
            return head;
        }
      	// 将哑节点链接到 head 前
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        
        // 将 prev 迭代到翻转区间首节点的前驱结点
        ListNode* prev = dummy;
        for (int i = 1; i < m; i++) {
            prev = prev->next;
        }

        // 区间翻转
        head = prev->next;
        for (int i = m; i < n; i++) {
            ListNode* tmp = head->next;
            head->next = tmp->next;
            tmp->next = prev->next;
            prev->next = tmp;
        }

        // 恢复现场
        head = dummy->next; 
        delete dummy;
        return head;
    }
};

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