2020年4月上旬【算法讨论3】链表

[yudidi]

https://www.cnblogs.com/yudidi/p/12617339.html

3. 合并有序链表
4. 判断链表是否有环
   4.5. 142. Linked List Cycle II && 找出链表中环的位置
5. LRUCache的设计,实现和调试

[yudidi]

3. 合并有序链表

速记: 递归(用[1-3,2-4]发现递归结构) 或 迭代(dummyhead + cur遍历指针)

• 总结 Q: 什么时候应该引入dummyhead?
  引入dummy_head是因为不知道要返回的头节点是哪个。比如 删除节点 和 合并链表。

• 配套练习
  88. 合并两个有序数组
  148. 对链表进行排序
  归并排序
  你写个链表快排吧

• 踩坑
  如果不用dummyhead, 会出现2种情况，往空链表尾部添加节点和非空链表尾部添加节点，需要2套处理逻辑。没有考虑全面的话，代码会有问题。
  所以这里再次引入dummyhead统一处理逻辑。

4. 判断链表是否有环

直觉解法：用哈希表判断是否访问过。
速记: 快慢指针(1步2步)，每次距离缩短1步，一定会追及。
配套练习：无，因为主要是追及问题。

5. 返回链表中环的入口节点

直觉解法：用哈希表判断是否访问过，并返回这个重复访问的节点，就是环的入口节点。
速记:
编码: 快慢指针前进相遇或不相遇, 等速重放，再次相遇。记录是否有环。
证明: a = Nx + c。

• 编码中遇到的问题。
  相遇后进行重放时，如何区分是相遇退出循环还是没有环退出的循环。
  1.判断 s==f 说明是相遇退出，但是这个判断对于空链表和单节点链表也是true，所以需要单独处理，容易遗漏产生bug。比如case([1] 1)
  2.增加一个标记has,有环则标记为true，相比方法1这个不需要考虑特殊情况。
• 配套练习：以下是官方给的相似题目，可以不做，因为很难想到这个关联。
  数组中重复的数字 && 287. Find the Duplicate Number 配套练习的这个题解说得不错
  剑指offer-面试题03. 数组中重复的数字
  以上2题是同一题，一个leetcode, 一个剑指offer。

其他练习

实现求链表的中间结点

[yudidi]

TODO

1. 递归专项讲解
2. a = Nx + c, 为什么要这么证明，如果知道自己的推导目标就是这样的？
3. 纸上写代码。是只写伪代码还是写能编译通过的代码，如何把握尺度(询问面试官)???