public class Solution { 
	public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 
	//先存储A链表的所有结点，在遍历B链表。所以空间复杂度来到了O(m),A有m个节点的话
		Set<ListNode> visited = new HashSet<ListNode>(); 
		ListNode temp = headA; 
		while (temp != null) { 
			visited.add(temp); 
			temp = temp.next; 
		} 
		temp = headB; 
		while (temp != null) { 
			if (visited.contains(temp)) { return temp; } 
			temp = temp.next; 
		} 
		return null; 
	} 
} 

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