# 0160. Intersection of Two Linked Lists
###### tags: `Leetcode` `FaceBook` `Easy` `Linked List`
Link: https://leetcode.com/problems/intersection-of-two-linked-lists/
## 思路 O(M+N) O(1) M,N是两个linked list的长度
暴力解法是先遍历一个，然后把所有node都加到set里面，遍历第二个的时候，如果set里面有这个当前node，就直接返回，但这样的空间复杂度是O(N)

或者就是知道两个list的长度差之后，让长的那个先往前走长度差那么多，也就是让两个list剩下的长度一样，然后一起往前走，如果碰到一样的，就返回，但这样要pass两次

大神解法的时间复杂度是O(1) 具体为什么这个解法成立 看[这里](https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49785/Java-solution-without-knowing-the-difference-in-len!)
## Code

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA, b = headB;
        while(a!=b){
            if(a!=null) a = a.next;
            else a = headB;
            if(b!=null) b = b.next;
            else b = headA;
            if(a==null && b==null) break;
        }
        return a;
    }
}