https://leetcode-cn.com/problems/middle-of-the-linked-list/solution/kuai-man-zhi-zhen-zhu-yao-zai-yu-diao-shi-by-liwei/


重点题目

876. 链表的中间结点

  • 这题很基础，一定要把算法细节理解好

两个考点

  • 指针的修改
    • 最典型的就是链表反转，反转链表 II。
  • 链表的拼接
    • 比如再比如合并有序链表等。

三个注意

  • 出现了环，造成死循环。
  • 分不清边界，导致边界条件出错。

  • 搞不懂递归怎么做

    • 可以看出，这两种写法不管是边界，入参，还是代码都不太一样。为什么会有这样的差异呢？
    • 如果是前序遍历，那么你可以想象前面的链表都处理好了，怎么处理的不用管。相应地如果是后序遍历，那么你可以想象后面的链表都处理好了，怎么处理的不用管。
    • 准确地说应该是前序遍历容易改成不需要栈的递归，而后续遍历需要借助栈来完成。

    • 前序遍历

      1. def dfs(head, pre):
      2. if not head: return pre
      3. next = head.next
      4. # # 主逻辑（改变指针）在后面
      5. head.next = pre
      6. dfs(next, head)

    • 后续遍历

      1. def dfs(head):
      2. if not head or not head.next: return head
      3. res = dfs(head.next)
      4. # 主逻辑（改变指针）在进入后面的节点的后面，也就是递归返回的过程会执行到
      5. head.next.next = head
      6. head.next = None
      8. return res

      技巧

  • DummyHead

    • 将头节点变成中间节点，简化判断。
    • 通过在合适的时候断开链接，返回链表的中间节点。
  • 快慢指针
    • 获取数组中间项和倒数第几项等特定元素

题型

链表指针的修改

经典题目

86. 分隔链表 (多练)

迭代自己写出来了，但是模模糊糊的。
答案

  • 将链表分成两段
  • 最后和起来

  • 返回最小的头

    328. 奇偶链表

    和86题解法一样，分两个链表组合，最后将两个链表首尾相连。

    206. 反转链表

    92. 反转链表 II（多练）

  • 使用stack

  • 或者头插法

    25. K 个一组翻转链表(多练)

    答案：

  • 节点搜索+指针的修改

  • 快慢指针分组

  • 然后按组翻转，这里得小心，这里是本题的难点。

    合并多个链表

    21. 合并两个有序链表

    迭代写法很简单。
    递归写法

  • 就后序遍历，遍历到最后一个

    删除节点

    237. 删除链表中的节点

    public void deleteNode(ListNode node) {
  node.val = node.next.val;
  node.next = node.next.next;
}

    203. 移除链表元素

    答案

  • 使用DummyHead方便删除头结点

  • 保留prev和curr指针，判断是否删除curr

    83. 删除排序链表中的重复元素

    答案

  • 迭代很简单

    82. 删除排序链表中的重复元素 II (多练)

    答案

  • 保留prev节点一定是没有重复的列表的尾端

  • 通过curr 和 curr.next 判断重复元素

    • 若是重复，找到第一个不重复的元素
    • prev.next

      链表排序

      48. 排序链表（多练，迭代）

      答案：

  • 归并排序。快排不行，需要拿到左边的尾节点，所以不是nlogn

  • 递归的mege sort更好写

    147. 对链表进行插入排序

    答案：

  • 使用dummyHead，方便在头节点之前插入节点

  • 将头节点当作第一个sorted节点，然后他的下一个就是需要排序的节点
  • 如果下一个节点，比以排序完的最后一个节点大，之间向后移一步

  • 从前向后遍历插入位置，找到后就插入，不必向后移，因为我们把要插入的节点放到前面去了。

    708. 循环有序列表的插

    答案一：

  • 先找到最小的节点

  • 然后开始寻找插入为止，保留prev和curr节点，插入在中间。

答案二：

  • do while 循环
  • 退出条件为 节点又回到头节点了 此时搜完了所有可以插入的地方
  • 保持一个变量，表示有无插入过。

  • 在退出循环后，如果未插入过，则插入在头节点后面。

    头插法

    尾插法

    链表节点的查询

    环形链表

    141. 环形链表

    快慢指针
    Floyd 判圈算法

    142. 环形链表 II(多练)

    快慢指针
    Floyd 判圈算法
    https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/
    答案

  • 快慢指针环内相遇

  • 慢指针和头指针相遇点即是答案

    经典题型

    160. 相交链表(Tricky)

    答案

  • 走到尽头见不到你，于是走过你来时的路，等到相遇时才发现，你也走过我来时的路。

  • https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/intersection-of-two-linked-lists-shuang-zhi-zhen-l/

    19. 删除链表的倒数第 N 个结点

    答案

  • 快慢指针+保留prev

    876. 链表的中间结点 (多练)

    答案

  • 快慢指针

    • 用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步，fast 一次走两步。
    • 将最后的NULL也当作一个节点，会有以下两种情况
      • 偶数个节点：
        • 算上最后的NULL节点会有2N次可以走
        • 此时，快指针每次走两步，慢指针每次走一步，共N个迭代
        • 终止条件为 fast == NULL 表示快指针到头了
        • 此时slow走了N步，位于第N+1个节点，符合正确答案。
      • 奇数个节点：
        • 假设就比上个例子的偶数个节点多了一个节点
        • Fast会走到下图5的位置，也就是之前NULL的位置。
        • 这时候，slow移动了N个，到达了节点N+1，这已经是正确答案了
        • 所以，我们fast要让停在这里，终止条件就是fast.next == null
    • 结合以上的两种情况：我们一开始无法得知链表长度的奇偶性，但当我们遇到fast==null或者fast.next==null的时候就一定表示，slow到达正确答案的位置了。而且若fast==null表示链表长度为偶数，fast!=null表示链表长度为奇数。
    • 总结如下图：

image.png

public ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

复合题型

234. 回文链表(多练)

答案

  • 节点搜索+指针的修改
  • 快慢指针走到中点。同时保留一个prev指针用于给慢指针反转链表。通过fast判断链表长度的奇偶性
    • fast == null -> even
    • fast != null -> odd

  • 第一次复习：不会做了。

    143. 重排链表 (多练)

  • 先找到中点

  • 反转中点后的链表

  • 合并两个链表

    61. 旋转链表

    答案：

  • 找到倒数k个节点，然后重新拼接

    Tricky

    138. 复制带随机指针的链表（多练）

  • 三步走

    • 在原链表中，将副本放在左边。
    • 通过原链表将副本的radom连起来
    • 最后将副本抽出来再将next连起来

      146. LRU 缓存机制(多练)

      写了我将近两个小时。。。
      答案：

  • 伪头节点 + 伪尾节点 互相连起来

  • 四个辅助函数

2. 两数相加