【小白笔记】反转链表 II

处理链表区间反转的关键在于：找到待反转区间的前驱节点，并将该区间内的节点逐个“移到”前面。

1. 解题思路：一次遍历（穿针引线法）

为了简化边界条件（比如从第一个节点就开始反转），我们通常先创建一个虚拟头节点 (Dummy Node)。

1. 定位前驱节点：移动指针pre到待反转区间的前一个位置（第left - 1个节点）。
2. 设置当前操作指针：cur指向区间的第一个节点，next指向cur的下一个节点。
3. 循环进行头插法：执行right - left次操作。每次将next节点插入到pre之后，从而实现局部反转。

2. 代码实现 (Python)

# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defreverseBetween(self,head:Optional[ListNode],left:int,right:int)->Optional[ListNode]:# 1. 设置 dummy node 防止 head 被反转的特殊情况dummy=ListNode(0)dummy.next=head pre=dummy# 2. 找到 left 的前一个节点for_inrange(left-1):pre=pre.next# 3. 开始局部反转cur=pre.nextfor_inrange(right-left):next_node=cur.next# 将 next_node 从链表中摘除，插入到 pre 后面cur.next=next_node.nextnext_node.next=pre.nextpre.next=next_nodereturndummy.next

3. 测试用例与结果

测试用例 1

• 输入:head = [1, 2, 3, 4, 5],left = 2,right = 4
• 过程简述:
  1. pre指向节点1。
  2. 第一次循环：把3提到1后面。链表变为1 -> 3 -> 2 -> 4 -> 5。
  3. 第二次循环：把4提到1后面。链表变为1 -> 4 -> 3 -> 2 -> 5。
• 预期输出:[1, 4, 3, 2, 5]

测试用例 2

• 输入:head = [5],left = 1,right = 1
• 预期输出:[5]

4. 复杂度分析

• 时间复杂度:O(N)O(N)O(N)，其中NNN是链表长度。我们只需要遍历一次链表。
• 空间复杂度:O(1)O(1)O(1)，我们只使用了常数级别的额外指针空间。

在 Python 中，for _ in range(n):是一种非常地道的写法，主要用于“只需要循环执行特定次数，但并不关心当前循环到第几次”的场景。

1. 下划线_的含义

在 Python 中，下划线_是一个约定俗成的占位符。

• 通常for i in range(5):中的i会存储当前循环的索引（0, 1, 2…）。
• 如果你在循环体内部完全不需要用到这个索引数字，使用_可以告诉阅读代码的人：“这个变量不重要，我只是想让这段代码运行nnn次。”

1. 为什么要定义dummy(虚拟头节点)？

在处理链表问题时，dummy节点就像是一个“救生圈”，它的主要作用是消除边界条件的特殊处理。

• 如果没有dummy：
  如果left = 1，意味着你要从原链表的第一个节点开始反转。此时，反转后的“新头节点”会发生变化。你需要写额外的if...else逻辑来处理“头节点被改变”的情况。
• 有了dummy：
  我们将dummy.next指向head。无论你反转的是中间一段，还是从第一个节点开始反转，head节点都变成了“中间某个节点”。
  最终结果只需返回dummy.next，它永远指向反转后正确的起始位置，逻辑变得整洁统一。

2. 为什么用循环去找？（链表 vs 数组）

这正是由链表的物理结构决定的：

数组 (Python 的 List)

• 特性：连续内存存储。
• 查找：支持“随机访问”。你可以直接通过下标arr[i]在O(1)O(1)O(1)时间内找到任何元素，就像查字典的页码一样快。
• 缺点：插入或删除中间元素时，需要挪动后面的所有元素，非常费力。

链表 (Linked List)

• 特性：分散内存存储，节点之间靠指针（地址）连接。
• 查找：不支持随机访问。你想找第nnn个节点，必须从第一个节点开始，顺着next指针一个一个数过去（即你看到的for循环）。这就是O(N)O(N)O(N)的查找时间。
• 优点：只要你找到了位置，插入和删除操作只需要改变指针指向，不需要移动数据，非常高效。

3. “定位到前一个”的必要性

在链表中，如果你想删除或移动节点B，你手里必须握着节点A（B的前驱节点）的指针。

• 因为链表是单向的，如果你直接跳到了left位置，你无法回过头去修改left-1节点的next指向。
• 所以，我们必须“未雨绸缪”，让pre停在left的前一个位置，这样我们才能把后面反转好的部分重新接回到主链表上。

总结对比

一句话总结：链表就像玩“寻宝游戏”，每一关只给你下一关的线索，所以你想去哪都得从第一关开始闯；而数组就像是有门牌号的公寓，你可以直接瞬移到任何一间房。