题目

分析

• 立马就能想到的方法是用哈希集合来记录，然而这样空间复杂度是O(n)
• 有一个巧妙地方法
• 记录两个头结点，如果节点不相等，每次循环向后移动指针，如果一方指向null就将这个指针指向另一边的头结点
• 如果相等就是找到了或者没有返回null（Java中null==null）

题解

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA;
        ListNode b = headB;
       while(a!=b){
           a = ((a==null)?headB:a.next);
           b = ((b==null)?headA:b.next);
       }
       return a;
    }
}

时间复杂度	空间复杂度
O(n)	O(1)

一点屁话

• 一种巧妙的方法，见过就会了
• 本来刚做完这题，一刷新就变成每日一题了:>