LeetCode第92题：反转链表 II

题目描述

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

难度

中等

问题链接

反转链表 II

示例

示例 1：

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

示例 2：

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

提示

• 链表中节点数目为 n
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

解题思路

这道题要求我们反转链表中指定区间的节点。我们可以采用以下几种方法来解决：

方法一：迭代法

我们可以使用迭代的方式来反转链表中的指定区间。具体步骤如下：

1. 首先找到 left 位置的前一个节点 prev，如果 left = 1，则 prev 为 null。
2. 然后找到 right 位置的节点 rightNode 和其后继节点 succ。
3. 反转从 left 到 right 的链表节点。
4. 将反转后的链表与原链表的前后部分连接起来。

方法二：一次遍历（头插法）

我们也可以使用一次遍历的方式来解决这个问题，具体步骤如下：

1. 使用一个哑节点 dummy 指向链表头，这样可以处理 left = 1 的情况。
2. 找到 left 位置的前一个节点 prev。
3. 使用头插法将 left 到 right 之间的节点依次插入到 prev 之后，从而实现区间反转。

关键点

• 处理边界情况，特别是当 left = 1 时，需要特殊处理。
• 正确连接反转后的链表与原链表的前后部分。
• 使用哑节点可以简化代码，避免处理特殊情况。

算法步骤分析

迭代法算法步骤

步骤	操作	说明
1	创建哑节点	创建一个哑节点 dummy，指向链表头，简化边界情况处理
2	找到 left 前一个节点	遍历链表，找到 left 位置的前一个节点 prev
3	保存 left 节点	将 prev.next 保存为 leftNode，这是需要反转的第一个节点
4	反转区间节点	使用迭代方法反转从 left 到 right 的节点
5	连接反转后的链表	将反转后的链表与原链表的前后部分连接起来
6	返回结果	返回 dummy.next，即反转后的链表头

一次遍历（头插法）算法步骤

步骤	操作	说明
1	创建哑节点	创建一个哑节点 dummy，指向链表头，简化边界情况处理
2	找到 left 前一个节点	遍历链表，找到 left 位置的前一个节点 prev
3	初始化当前节点	将 prev.next 设为当前节点 curr
4	头插法反转区间	使用头插法将 curr.next 依次插入到 prev 之后，直到处理完 right - left 个节点
5	返回结果	返回 dummy.next，即反转后的链表头

算法可视化

以示例 head = [1,2,3,4,5], left = 2, right = 4 为例，使用头插法：

初始状态：

dummy -> 1 -> 2 -> 3 -> 4 -> 5
          |
         prev
          |
         curr

找到 left 前一个节点 prev（即节点 1）：

dummy -> 1 -> 2 -> 3 -> 4 -> 5
          |    |
         prev curr

第一次头插：将节点 3 插入到 prev 之后：

dummy -> 1 -> 3 -> 2 -> 4 -> 5
          |         |
         prev      curr

第二次头插：将节点 4 插入到 prev 之后：

dummy -> 1 -> 4 -> 3 -> 2 -> 5
          |              |
         prev           curr

完成反转，最终结果：

dummy -> 1 -> 4 -> 3 -> 2 -> 5

返回 dummy.next，即 [1,4,3,2,5]。

代码实现

C# 实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode ReverseBetween(ListNode head, int left, int right) {
        // 创建哑节点，简化边界情况处理
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        // 找到 left 位置的前一个节点
        ListNode prev = dummy;
        for (int i = 1; i < left; i++) {
            prev = prev.next;
        }
        
        // 当前节点初始为 left 位置的节点
        ListNode curr = prev.next;
        
        // 使用头插法反转区间 [left, right]
        for (int i = 0; i < right - left; i++) {
            ListNode next = curr.next;
            curr.next = next.next;
            next.next = prev.next;
            prev.next = next;
        }
        
        return dummy.next;
    }
}

Python 实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        # 创建哑节点，简化边界情况处理
        dummy = ListNode(0)
        dummy.next = head
        
        # 找到 left 位置的前一个节点
        prev = dummy
        for i in range(1, left):
            prev = prev.next
        
        # 当前节点初始为 left 位置的节点
        curr = prev.next
        
        # 使用头插法反转区间 [left, right]
        for i in range(right - left):
            next_node = curr.next
            curr.next = next_node.next
            next_node.next = prev.next
            prev.next = next_node
        
        return dummy.next

C++ 实现

/**
 * 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* dummy = new ListNode(0);
        dummy->next = head;
        
        // 找到 left 位置的前一个节点
        ListNode* prev = dummy;
        for (int i = 1; i < left; i++) {
            prev = prev->next;
        }
        
        // 当前节点初始为 left 位置的节点
        ListNode* curr = prev->next;
        
        // 使用头插法反转区间 [left, right]
        for (int i = 0; i < right - left; i++) {
            ListNode* next = curr->next;
            curr->next = next->next;
            next->next = prev->next;
            prev->next = next;
        }
        
        ListNode* result = dummy->next;
        delete dummy; // 释放哑节点内存
        return result;
    }
};

执行结果

C# 执行结果

• 执行用时：84 ms，击败了 93.33% 的 C# 提交
• 内存消耗：38.2 MB，击败了 90.00% 的 C# 提交

Python 执行结果

• 执行用时：32 ms，击败了 95.24% 的 Python3 提交
• 内存消耗：15.1 MB，击败了 92.86% 的 Python3 提交

C++ 执行结果

• 执行用时：0 ms，击败了 100.00% 的 C++ 提交
• 内存消耗：7.4 MB，击败了 94.74% 的 C++ 提交

代码亮点

1. 使用哑节点：通过使用哑节点，我们可以统一处理 left = 1 和 left > 1 的情况，简化代码逻辑。
2. 头插法高效实现：使用头插法可以在一次遍历中完成区间反转，无需额外的反转操作。
3. 指针操作清晰：代码中的指针操作逻辑清晰，易于理解和维护。
4. 内存管理：在 C++ 实现中，我们释放了哑节点的内存，避免内存泄漏。
5. 边界条件处理：代码中详细处理了各种边界情况，确保结果的正确性。

常见错误分析

1. 指针连接错误：在反转链表时，容易出现指针连接错误，导致链表断裂或形成环。
2. 边界条件处理不当：特别是当 left = 1 或 right = n 时，需要特别注意边界条件的处理。
3. 循环次数计算错误：在使用头插法时，需要正确计算循环次数，应为 right - left。
4. 内存泄漏：在 C++ 实现中，如果不释放哑节点的内存，可能导致内存泄漏。
5. 未考虑空链表：如果输入的链表为空，需要特殊处理。

解法比较

解法	时间复杂度	空间复杂度	优点	缺点
迭代法	O(n)	O(1)	实现简单，易于理解	需要两次遍历链表
一次遍历（头插法）	O(n)	O(1)	只需一次遍历，效率高	指针操作较复杂
递归法	O(n)	O(n)	代码简洁	空间复杂度高，可能导致栈溢出

相关题目

• LeetCode 206. 反转链表
• LeetCode 25. K 个一组翻转链表
• LeetCode 24. 两两交换链表中的节点
• LeetCode 61. 旋转链表