力扣小白刷题之160题相交链表
题目描述
编写一个程序，找到两个单链表相交的起始节点。
注意：
- 如果两个链表没有交点，返回 null
- 在返回结果后，两个链表仍需保持原有的结构
- 可假定整个链表结构中没有循环
- O(n) 时间复杂度 O(1)内存
思路
参考：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/tu-jie-xiang-jiao-lian-biao-by-user7208t/ 的评论区
- 我先走我的路，再走你的路，你先走你的路，再走我的路，这样咱俩走的路程就一样了，速度一样，那么肯定在在咱俩两条路的交叉口相遇，并一起走向终点。
- 若相交，链表A：a + c，链表B：b + c，a + c + b + c = b + c + a + c。则会在公共点 c 处相遇。若不香蕉，a + b = b + a。因为此处相遇处是 null。
- 比较长的链表的指针指向比较短的链表的 head 时，长度差就消除了。