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