【leetcode】160.（Easy）Intersection of Two Linked Lists

解题思路：

我的想法是，设置两个指针，将所有指针走过的节点都放到一个map里，map里出现的第一个重复的节点就是交叉节点。
但是运行下来发现费时间也费空间。


看到 评论区有的大神的做法是：
两个链表：
第一串链表的表示是：路径A+路径C
第二串链表的表示是：路径B+路径C
那可以设置两个指针：
第一个指针走的路径是：路径A+路径C+路径B
第二个指针走的路径是：路径B+路径C+路径A
两个指针第一次相遇的节点就是交叉节点


这个做法是常量的空间复杂度和线性的时间复杂度

最初的做法：

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Map<ListNode,Integer> map=new HashMap<>();
        
        ListNode p1=headA;
        ListNode p2=headB;
        while(p1!=null||p2!=null) {
        	if(p1!=null) {
        		if(map.containsKey(p1))	return p1;
        		map.put(p1, 1);
        		p1=p1.next;
        	}
        	if(p2!=null) {
        		if(map.containsKey(p2)) return p2;
        		map.put(p2,1);
        		p2=p2.next;
        	}
        }
        return null;
    }
}

运行结果：



第二种做法：

class Solution{
	public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
		if(headA==null||headB==null)	return null;
		ListNode p1=headA;
		ListNode p2=headB;
		
		while(p1!=p2) {
			p1=p1==null?headB:p1.next;
			p2=p2==null?headA:p2.next;
		}
		return p1;
	}
}

运行结果：