查找兩個(gè)鏈表的第一個(gè)公共子節(jié)點(diǎn)

• 原題：Leetcode CR 171. 訓(xùn)練計(jì)劃 V

題目說(shuō)明：

輸入兩個(gè)鏈表，找出它們的第一個(gè)公共結(jié)點(diǎn)。

兩個(gè)鏈表的頭結(jié)點(diǎn)都是已知的，相交之后成為一個(gè)單鏈表，但是相交的位置未知，并且相交之前的結(jié)點(diǎn)數(shù)也是未知的，請(qǐng)?jiān)O(shè)計(jì)算法找到兩個(gè)鏈表的合并點(diǎn)

---

（1）暴力求解法

思路：通過(guò)冒泡的方式來(lái)遍歷兩個(gè)鏈表，將第一個(gè)鏈表中的每一個(gè)結(jié)點(diǎn)依次與第二個(gè)鏈表的每一個(gè)結(jié)點(diǎn)進(jìn)行比較，當(dāng)出現(xiàn)相同的結(jié)點(diǎn)指針，即為相交結(jié)點(diǎn)

注意：該方法雖然簡(jiǎn)單好理解，但是如果要考慮時(shí)間復(fù)雜度，暴力求解法一般都是最慢的，耗時(shí)最高的

/*** 1.暴力求解，循環(huán)遍歷兩個(gè)鏈表，判斷結(jié)點(diǎn)相同* @param headA* @param headB* @return*/
public static ListNode findFirstCommonNodeByViolence(ListNode headA, ListNode headB) {// 每一個(gè)結(jié)點(diǎn)進(jìn)行比較，判斷是否相同ListNode A = headA;ListNode B = headB;while (A != null) {while (B != null) {if (A == B) {return A;}B = B.next;}B = headB;A = A.next;}return null;
}

---

（2）使用哈希Hash?

思路：將第一個(gè)鏈表的元素全部存入到HashMap里面，然后一邊遍歷第二個(gè)鏈表，一邊檢查當(dāng)前元素是否在HashMap中

提示：Java中的Map包含containsKey等方法，可以檢測(cè)該Map中是否包含該元素

 /*** 2.使用Hash的方法* @param headA* @param headB* @return*/
public static ListNode findFirstCommonNodeByMap(ListNode headA, ListNode headB) {Map<ListNode, Integer> hashMap = new HashMap<>();while (headA != null) {hashMap.put(headA, null); // 鏈表中的所有結(jié)點(diǎn)存入HashMap中headA = headA.next;}while (headB != null) {if (hashMap.containsKey(headB)) { // 判斷HashMap中是否包含headB，包含說(shuō)明找到了公共結(jié)點(diǎn)，直接返回即可return headB;}headB = headB.next;}return null;
}

---

（3）使用集合? - 與Hash類似

思路：本質(zhì)其實(shí)和哈希Hash沒(méi)有太大區(qū)別，只是換了一個(gè)存儲(chǔ)的空間，將所有的結(jié)點(diǎn)存入到集合中，然后一邊遍歷，一邊檢查當(dāng)前元素是否在HashSet中

問(wèn)題：為什么使用Set，而不使用其他集合，如List等等

解釋：并不是說(shuō)不可以使用List集合，相反可以使用List集合，也是可以的，但是List集合的運(yùn)行時(shí)間和第一種暴力求解法沒(méi)有什么區(qū)別，這是由于List集合是有序的，每次存進(jìn)去其實(shí)還會(huì)需要記錄一個(gè)相當(dāng)于sort排序的值，它第幾個(gè)進(jìn)來(lái)的，這個(gè)也是會(huì)占用內(nèi)存，導(dǎo)致運(yùn)行時(shí)間變長(zhǎng)，而Set集合是無(wú)序的，不需要記錄一個(gè)sort值，因此使用Set的速度就快，并且我們追進(jìn)HashSet的源碼進(jìn)去查看，可以發(fā)現(xiàn)HashSet其實(shí)就是new HashMap對(duì)象，也就是HashSet就是HashMap，跟哈希Hash是沒(méi)有本質(zhì)區(qū)別的

/*** 3.使用集合的方法* @param headA* @param headB* @return*/
public static ListNode findFirstCommonNodeBySet(ListNode headA, ListNode headB) {Set<ListNode> set = new HashSet<>();// 循環(huán)遍歷head1，將head1所有元素存到set中while (headA != null) {set.add(headA);headA = headA.next;}// 循環(huán)遍歷head2，判斷set集合鏈表是否包含head2while (headB != null) {if (set.contains(headB)) {return headB;}headB = headB.next;}return null;
}

（4）使用棧?

思路：將兩個(gè)鏈表分別存入到兩個(gè)棧中，兩邊同時(shí)出棧，判斷是否一致，如果一致則說(shuō)明存在相交，那么我們就繼續(xù)查找，直到不一致，說(shuō)明相同的結(jié)點(diǎn)都已經(jīng)出棧了，就已經(jīng)找到了兩個(gè)鏈表的公共結(jié)點(diǎn)

提示：棧是后進(jìn)先出，存進(jìn)去后相同的都在后面，因此相同的結(jié)點(diǎn)也就是存在棧頂

/*** 4.通過(guò)棧的方法* @param headA* @param headB* @return*/
public static ListNode findFirstCommonNodeByStack(ListNode headA, ListNode headB) {Stack<ListNode> stackA = new Stack();Stack<ListNode> stackB = new Stack();while (headA != null) {stackA.push(headA); // 存入棧中headA = headA.next;}while (headB != null) {stackB.push(headB); // 存入棧中headB = headB.next;}ListNode preNode = null;while (stackB.size() > 0 && stackA.size() > 0) {// 由于存是從頭存到底部，因此后面的結(jié)點(diǎn)都是相同的，當(dāng)取出來(lái)是不一樣的時(shí)候，說(shuō)明從公共結(jié)點(diǎn)分隔出去了，到分岔口了，那就直接break即可if (stackA.peek() == stackB.peek()) { // peek表示查看此堆棧頂部的對(duì)象，但是不會(huì)刪除，而pop是直接返回了，也就刪除了preNode = stackA.pop();stackB.pop();} else {break;}}return preNode;
}

（5）仍有更多方法，作者尚未理解，理解會(huì)發(fā)出