LeetCode 题解：链表

链表结构，天生具有递归性，我们尝试一下递归思维，解决最普遍的题目，反转链表。

前序遍历之中，你可以想象，前面的链表都已经处理好了，只需要改变后面的链表就行。

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    def dfs(curr, prev):
        # 最后返回尾节点
        if not curr: return prev
        next = curr.next
        # 主逻辑：每次递归只改变一个箭头
        curr.next = prev
        return dfs(next, curr)
    return dfs(head, None)

后序遍历则与之相反，你可以想象，后面的链表都已经处理好了，只需要改变前面的链表就行。

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    def dfs(curr):
        # 边界条件
        if not curr or not curr.next: return curr
        # 后序遍历
        ret = dfs(curr.next)
        # 主逻辑
        curr.next.next = curr
        # 现在先置空并没有关系，因为 dfs 过程结束后会自动回推一格
        curr.next = None
        return ret
    return dfs(head)

考点：

1. 指针的修改
2. 链表的拼接

需要注意：

1. 生成环
2. 没搞清边界

技巧：

1. 虚拟头
2. 快慢指针
3. 拼接链表

做题策略

1. 先穿针引线
2. 再排列组合
3. 排除潜在的空指针异常

归类题解

链表概念

• [707] 构建链表类
  • 比较平铺直叙，但如果完全不加辅助变量还是有一点点难的
  • 强烈不建议以本类直接储存数据
  • 需要考虑大量的边界条件
    • 任何对本节点的操作（查询、删除等），都需要考虑本节点是否为空
    • 插入尾节点，插入（和删除）第 i 节点时需要使用虚拟头，因为 i 可能等于 0，尾节点也可能什么都没有
    • k 次循环迭代时，我们不希望给出的节点为空，因此当下一节点为空的时候，跳出循环

快慢指针

• [876] 链表中点
  • 快慢指针母题，需要注意边界条件，因为快指针一次前进两格，边界条件就是 快指针自己和快指针下一格都非空
• [141] 链表环1, [142] 链表环2
  • 我们希望求得的值是链表环的起点下标 a ，我们假设快慢指针相遇时慢指针走了 a + b 步，那么慢指针就走了 2a + 2b 步，环长为 n = a + b 步
  • 那么我们的慢指针已经走了 a + b 步，想要求得 a ，我们可以考虑 a + n = a + a + b ，再找第三根指针，与慢指针同步，两者相遇时，第三根指针走过的步数，就是环的起点
• [1721] 交换链表中左数第 k 个和右数第 k 个元素
  • 双指针，指针ABC都从头开始，指针A和B从左往右走k次，然后指针B和指针C同步一直走到头，再交换指针A和C

穿针引线

• [206] 反转链表, [92] 反转从 m 到 n 之间的链表
  • 反转链表的迭代写法较为直观，画图即可，递归写法见文首遍历链表
  • 比较容易记忆的反转链表做法，一般都需要虚拟头
• [24] 交换节点
  • 无脑虚拟头，无脑画图
  • 考点：指针向下推进到哪个节点？
• [21] 归并排序两个链表, [23] 归并排序 k 个链表, [148] 排序链表
  • 使用虚拟头归并两个链表，使用递归归并 k 个链表
  • 考点：如果使用归并排序的话，要注意取中点的时候，快指针不需要走到头
• [61] 向右把链表旋转 k 步
  • 题眼： k 有可能大于列表长度，因此需要先求出列表长度，再旋转
  • 考点：需要注意 corner case ：链表长度为 0 ， k 为 0
• [86] 链表按给定值二分，再拼接
  • 考点： 避免成环 ：后半部分链表的尾端，箭头需要置空

节点操作

• [82] 删除重复节点（含自己）, [83] 删除重复节点（不含自己）
  • 不含自己的话我们每次遇到 next 与自己值相同的节点就删除
  • 含自己也删的话需要使用虚拟头，每次遇到下两个节点值相同时，保存这一值，并删除后面所有与此值相同的节点
• [203] 删除有给定值的节点
  • 考点：虚拟头
• [237] 只给定链表的一个节点的指针，删除这一节点
  • 把下一节点的值挪到这一节点上，再删除下一节点
• [2] 两数相加
  • 考点：当其中一个列表已经加完的时候，还带着进位的话，存在无限进位的可能（即 1 + 999...9 = 1000...0 ）
  • 既然我们已经考虑过了无限进位，在无限进位之后还带着进位的话，直接在答案末尾加 1 即可

难题

• [25] k 个一组反转链表
  • 考点：
• [138] 随机指针，复制链表
  • 考点：
• [143] 重构链表
  • 考点：
• [147] 插入排序链表
  • 考点：
• [160] 链表重叠
  • 考点：
• [234] 回文链表
  • 考点：