题目

https://leetcode-cn.com/problems/reverse-linked-list-ii/

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明: 1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4

输出: 1->4->3->2->5->NULL

程序

image.png
因为有可能反转第一个节点，所以创建一个哨兵节点 0
在反转的过程中，我们需要保存几个重要的指针，分别是：

  • 第一个反转点的上一个指针(记作：interrupts_node)，如上面的1，这个指针最终要指向反转后的第一个指针，如上面的4
  • 第一个反转点的指针（记作： first_reverse_node），如上面的2，这个指针最终要指向最后一个反转指针的下一个指针，如上面的5
  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  8. # 因为有可能反转第一个节点，所以创建一个哨兵节点
  9. class Solution:
  10.     def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
  11.         if not head:
  12.             return None
  13.         dummy = ListNode(0)
  14.         dummy.next = head
  15.         flag_p = dummy # 标志指针，帮助我们来找到要开始反转的那个节点的上一个节点
  16.         pos = 0  # 位置，记录当前走到哪个位置
  17.         while flag_p:
  18.             # 判断当前的位置是不是位置 m 的上一个位置
  19.             # 是的话
  20.             if pos == m - 1:
  21.                 interrupts_node = flag_p # 最终 interrupts_node 节点的 next 节点是反转区间的最后一个
  22.                 reverse_node = flag_p.next # 要反转的开始节点
  23.                 sub_cur = None # 子
  24.                 first_reverse_node = flag_p.next # 第一个反转点的指针 first_reverse_node，这个指针最终要指向最后一个反转指针的下一个指针
  25.                 while pos < n: # 如果当前位置在 小于位置 n，那么说明需要反转该节点
  26.                     # 下面就是常规的链表反转
  27.                     node = reverse_node.next  # 
  28.                     reverse_node.next = sub_cur
  29.                     sub_cur = reverse_node
  30.                     reverse_node = node
  31.                     pos += 1
  32.                 # 两个关键的指针需要指向正确的位置
  33.                 interrupts_node.next = sub_cur
  34.                 first_reverse_node.next = node
  35.                 break
  37.             # 不是的话往下走
  38.             flag_p = flag_p.next
  39.             pos += 1
  40.         return dummy.next