2021 第 29 篇题解

92. 反转链表 II

题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/reverse-linked-list-ii/

题目

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

示例 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

进阶： 你可以使用一趟扫描完成反转吗？

解题思路

思路：头插法

在做此题前，可以先尝试 206. 反转链表，当理解 206 题后，相信回来会有助于理解本题。

在这道题中，题目给定一个单链表，包括以下参数：

• ：链表头节点

• ：整数，表示单链表位置 处

• ：整数，表示单链表位置 处

  其中，这里 。

题目要求：

• 反转位置 到位置 的链表节点，返回反转后的链表。

在这里，我们先以示例 1

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

以上图示来源：力扣

用动图的形式看下实现过程，再说明其中的做法，图示如下：

根据上面的图示，这里说下其中涉及的参数，以及其中反转过程中的步骤：

其中涉及的参数：

• ：哑节点，减少判断；
• ：指向 的前一个节点，反转过程中不变；
• ：初始指向需要反转区域的第一个节点，也就是   的位置；
• ：指向 的下一个节点，跟随 变化。

其中反转过程中的步骤：

1. 将 的下一个节点指向 的下一个节点；
2. 将 的下一个节点指向 的下一个节点；
3. 将 的下一个节点指向 。
4. 循环上面三个步骤，直至反转结束。

根据上面的步骤，实现的代码如下：

# 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_node = ListNode(-1)
        dummy_node.next = head
  
        # 令 pre 指向 left 位置的前一个节点
        pre = dummy_node
        for _ in range(left - 1):
            pre = pre.next
        
        cur = pre.next
        # 通过头插法，实现反转
        for _ in range(right - left):
            nxt = cur.next
            cur.next = nxt.next
            nxt.next = pre.next
            pre.next = nxt
                    
        return dummy_node.next

复杂度分析

• 时间复杂度： ， 表示链表节点总数。
• 空间复杂度： 。

欢迎关注

如有错误，烦请指出，欢迎指点交流。若觉得写得还不错，麻烦点个赞👍，谢谢。