問題描述
輸入兩個鏈表，找出它們的第一個公共節點。
如下面的兩個鏈表：
在節點 c1 開始相交。
示例 1：
輸入：intersectVal = 8,
listA = [4,1,8,4,5],
listB = [5,0,1,8,4,5],
skipA = 2, skipB = 3
輸出：Reference of the node with value = 8
輸入解釋：相交節點的值為 8 （注意，如果兩個列表相交則不能為 0）。從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B
為 [5,0,1,8,4,5]。在 A 中，相交節點前有 2 個節點；在 B 中，相交節點前有 3 個節點。
示例 2：
輸入：intersectVal = 2,
listA = [0,9,1,2,4],
listB = [3,2,4],
skipA = 3, skipB = 1
輸出：Reference of the node with value = 2
輸入解釋：相交節點的值為 2 （注意，如果兩個列表相交則不能為 0）。從各自的表頭開始算起，鏈表 A 為 [0,9,1,2,4]，鏈表 B
為 [3,2,4]。在 A 中，相交節點前有 3 個節點；在 B 中，相交節點前有 1 個節點。
示例 3：
輸入：intersectVal = 0,
listA = [2,6,4],
listB = [1,5],
skipA = 3, skipB = 2
輸出：null
輸入解釋：從各自的表頭開始算起，鏈表 A 為 [2,6,4]，鏈表 B 為 [1,5]。由于這兩個鏈表不相交，所以 intersectVal
必須為 0，而 skipA 和 skipB 可以是任意值。解釋：這兩個鏈表不相交，因此返回 null。
注意：
- 如果兩個鏈表沒有交點，返回 null.
- 在返回結果后，兩個鏈表仍須保持原有的結構。
- 可假定整個鏈表結構中沒有循環。
- 程序盡量滿足 O(n) 時間復雜度，且僅用 O(1) 內存。
通過集合set解決
上面說了一大堆，其實就是判斷兩個鏈表是否相交，如果相交就返回他們的相交的交點，如果不相交就返回null。
做這題最容易想到的一種解決方式就是先把第一個鏈表的節點全部存放到集合set中，然后遍歷第二個鏈表的每一個節點，判斷在集合set中是否存在，如果存在就直接返回這個存在的結點。如果遍歷完了，在集合set中還沒找到，說明他們沒有相交，直接返回null即可，原理比較簡單，直接看下代碼
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//創建集合set
Set<ListNode> set = new HashSet<>();
//先把鏈表A的結點全部存放到集合set中
while (headA != null) {
set.add(headA);
headA = headA.next;
}
//然后訪問鏈表B的結點，判斷集合中是否包含鏈表B的結點，如果包含就直接返回
while (headB != null) {
if (set.contains(headB))
return headB;
headB = headB.next;
}
//如果集合set不包含鏈表B的任何一個結點，說明他們沒有交點，直接返回null
return null;
}
123456789101112131415161718
先統計兩個鏈表的長度
還可以先統計兩個鏈表的長度，如果兩個鏈表的長度不一樣，就讓鏈表長的先走，直到兩個鏈表長度一樣，這個時候兩個鏈表再同時每次往后移一步，看節點是否一樣，如果有相等的，說明這個相等的節點就是兩鏈表的交點，否則如果走完了還沒有找到相等的節點，說明他們沒有交點，直接返回null即可，來畫個圖看一下。
最后再來看下代碼
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//統計鏈表A和鏈表B的長度
int lenA = length(headA), lenB = length(headB);
//如果節點長度不一樣，節點多的先走，直到他們的長度一樣為止
while (lenA != lenB) {
if (lenA > lenB) {
//如果鏈表A長，那么鏈表A先走
headA = headA.next;
lenA--;
} else {
//如果鏈表B長，那么鏈表B先走
headB = headB.next;
lenB--;
}
}
//然后開始比較，如果他倆不相等就一直往下走
while (headA != headB) {
headA = headA.next;
headB = headB.next;
}
//走到最后，最終會有兩種可能，一種是headA為空，
//也就是說他們倆不相交。還有一種可能就是headA
//不為空，也就是說headA就是他們的交點
return headA;
}
//統計鏈表的長度
private int length(ListNode node) {
int length = 0;
while (node != null) {
node = node.next;
length++;
}
return length;
}
雙指針解決
我們還可以使用兩個指針，最開始的時候一個指向鏈表A，一個指向鏈表B，然后他們每次都要往后移動一位，順便查看節點是否相等。如果鏈表A和鏈表B不相交，基本上沒啥可說的，我們這里假設鏈表A和鏈表B相交。那么就會有兩種情況，
一種是鏈表A的長度和鏈表B的長度相等，他們每次都走一步，最終在相交點肯定會相遇。
一種是鏈表A的長度和鏈表B的長度不相等，如下圖所示
雖然他們有交點，但他們的長度不一樣，所以他們完美的錯開了，即使把鏈表都走完了也找不到相交點。
我們仔細看下上面的圖，如果A指針把鏈表A走完了，然后再從鏈表B開始走到相遇點就相當于把這兩個鏈表的所有節點都走了一遍，同理如果B指針把鏈表B走完了，然后再從鏈表A開始一直走到相遇點也相當于把這兩個鏈表的所有節點都走完了
所以如果A指針走到鏈表末尾，下一步就讓他從鏈表B開始。同理如果B指針走到鏈表末尾，下一步就讓他從鏈表A開始。只要這兩個鏈表相交最終肯定會在相交點相遇，如果不相交，最終他們都會同時走到兩個鏈表的末尾，我們來畫個圖看一下
如上圖所示，A指針和B指針如果一直走下去，那么他們最終會在相交點相遇，最后再來看下代碼
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//tempA和tempB我們可以認為是A,B兩個指針
ListNode tempA = headA;
ListNode tempB = headB;
while (tempA != tempB) {
//如果指針tempA不為空，tempA就往后移一步。
//如果指針tempA為空，就讓指針tempA指向headB（注意這里是headB不是tempB）
tempA = tempA == null ? headB : tempA.next;
//指針tempB同上
tempB = tempB == null ? headA : tempB.next;
}
//tempA要么是空，要么是兩鏈表的交點
return tempA;
}
注意：這里所說的指針并不是C語言中的指針，在這里其實他就是一個變量，千萬不要搞混了。
問題分析
第一種解法應該是都容易想到的，但效率不高，一個個存儲，然后再拿另一個鏈表的節點一個個判斷。最后一種解法沒有統計鏈表的長度，而是當一個鏈表訪問完如果沒有找到相交點，就從下一個鏈表繼續訪問，一般不太容易想到，也算是比較經典的。
