题解一：

        哈希表：两链表出现的第一个相同的值就是相交节点，因此我们先用哈希记录链表A所有出现过的值，再遍历链表B查找哈希表，找出第一个相同的值即为结果。

import java.util.HashSet;

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> set = new HashSet();
        ListNode temp = headA;
        while (temp != null) {
            set.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while (temp != null) {
            if (set.contains(temp)) return temp;
            temp = temp.next;
        }
        return null;
    }
}

题解二：

        双指针遍历：以指针a，指针b分别遍历链表A和链表B。当指针a到达链表A末尾时，从链表B起点开始继续遍历；当指针b到达链表B末尾时，从链表A开始继续遍历。这样，如果两链表有相交点的话，指针ab会同时到达这个交点。

理由是链表AB具有相同段和不同段，记不同段为Ta、Tb，记相同段为Tc，则按上述步骤遍历至交点时，指针ab的路径Ta+Tc+Tb = Tb+Tc+Ta。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        ListNode a = headA;
        ListNode b = headB;
        while (true) {
            if (a == b)
                break;

            if (a != null) {
                a = a.next;
            } else {
                a = headB;
            }

            if (b != null) {
                b = b.next;
            } else {
                b = headA;
            }
        }
        return a;
    }
}