思路1

1. 链A的每个节点都遍历一遍链B，时间复杂度最高
   思路2
2. 链A的每个节点都存入map，然后遍历链B，如果map中存在则代表找到相同节点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {

    Map<ListNode,Integer> map = new HashMap();

    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode tmpA = headA;
        ListNode tmpB = headB;
        while(tmpA != null) {
            map.put(tmpA,1);
            tmpA = tmpA.next;
        }

        while(tmpB != null) {
           if(map.get(tmpB)!=null) return tmpB;
            tmpB = tmpB.next;
        }

        return null;

         
    }
}

思路3(比较精妙）

1. 这里可以根据A，B链的长度以及相交节点前的链长a,b分为四种情况

• A = B,a!= b，不存在这种情况
• A = B,a = b，这样两个指针一次遍历会直接相遇
• A != B, a!=b，指针第一次遍历后，再交换链表遍历会相遇。

例如相交节点长度为c，因为a!=b，因此第一次遍历时指针不会相遇，pA经过A+b个节点长度后会第二次到达相交节点；pB同理经过B+a个节点长度后会第二次到达相交节点。相交链表后的长度为c，则A=a+c,B=b+c;A+b = A+B-c,B+a = B+A-c，即pA和pB在第二次交换链表遍历的时候会在相交节点相遇（因为最后跑的路程是等长的，都是A+B）

• A != B, a = b ，这样两个指针一次遍历会直接相遇

2. 不相交的链表在循环结束后都会指向null

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 存在空节点，一定不可能相交
        if(headA == null || headB == null) return null;
        ListNode pA = headA;
        ListNode pB = headB;
        while(pA != pB) {
            // 同时移动两个指针，当第一次遍历结束后去遍历另一个链表
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

Q.E.D.