**今日刷题量：4 **
当前刷题总量：25
Easy: 14
Mid: 10
Hard: 1
Day 4
思想方法
1.一定要学会画图，思路捋不清楚的时候画图去拆解每一步的操作，再尝试用一个或多个指针去模拟
2.快慢指针找链表相交点
3.找环问题，Floyd判圈算法（龟兔赛跑算法）
第一阶段：检测环
慢指针：每次前进一步
快指针：每次前进两步
如果链表有环，快慢指针必定会在环内某点相遇
如果快指针到达 nullptr，说明链表无环
第二阶段：寻找环入口
数学推导：
设头节点到环入口距离：a
环入口到相遇点距离：b
相遇点到环入口距离：c
慢指针路程：a + b
快指针路程：a + b + c + b = a + 2b + c
由于快指针速度是慢指针2倍：2(a + b) = a + 2b + c
化简得：a = c
结论：从头节点和相遇点同时出发，以相同速度前进，会在环入口相遇
时间复杂度：O(n)
最坏情况下需要遍历整个链表
空间复杂度：O(1)，只使用了常数个指针
练习题目
-
- 两两交换链表中的节点（mid） ：https://leetcode.cn/problems/swap-nodes-in-pairs/description/
- 19.删除链表的倒数第N个节点 （mid） ：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/submissions/676731112/
- 02.07. 链表相交（easy） ：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
- 142.环形链表II （mid）：https://leetcode.cn/problems/linked-list-cycle-ii/