92. 反转链表 II

题目

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

示例 1：

92. 反转链表 II - 图1

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

示例 2：

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

提示：

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

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

题解

首先，基本的链表翻转很简单，只是这题要考虑不少的边界条件。
注意可能从head节点就开始反转，所以通过哨兵节点来简化。
image.png

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
  8.         p0=ListNode(0,head)
  9.         p=p0
  10.         for i in range(left-1):
  11.             p=p.next
  12.         pre=p
  13.         p1=p
  14.         p=p.next
  15.         for i in range(left,right+1):
  16.             next=p.next
  17.             p.next=pre
  18.             pre=p
  19.             p=next
  20.         p1.next.next=p
  21.         p1.next=pre
  22.         return p0.next

官方题解

class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        # 设置 dummyNode 是这一类问题的一般做法
        dummy_node = ListNode(-1)
        dummy_node.next = head
        pre = dummy_node
        for _ in range(left - 1):
            pre = pre.next

        cur = pre.next
        for _ in range(right - left):
            next = cur.next
            cur.next = next.next
            next.next = pre.next
            pre.next = next
        return dummy_node.next

官方的程序和我的有一点点区别，我是把 curr 指向 pre，它是把 curr.next 指向 curr 。
如果是我来写的话，我肯定这样写：

next=curr.next
curr.next=next.next
next.next=curr
pre.next=next
pre=curr
curr=next

但实际上我们其实需要的是 curr.next 和 pre.next，curr和 pre其实是可以隐去的。
这样的话，就进一步简化了代码，这也太简炼了，不愧是官方代码。
image.png