題目描述：

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

分析：

思路一：暴力解法准夷，強(qiáng)烈不建議！
遍歷第一個鏈表的每個節(jié)點(diǎn)莺掠，同時每次都遍歷一遍另一個鏈表衫嵌，看是否有節(jié)點(diǎn)和這個節(jié)點(diǎn)相同，如果有相同節(jié)點(diǎn)就是公共節(jié)點(diǎn)彻秆，如果沒有楔绞，就繼續(xù)向下遍歷结闸。

思路二：長鏈表先走，再同步遍歷
兩個鏈表比較長短酒朵，計(jì)算出兩者的長度差x桦锄，比較長的鏈表先往前走x步，然后長短鏈表一起同步向前走蔫耽，看遍歷到的節(jié)點(diǎn)是否相同结耀，如果相同就是第一個公共節(jié)點(diǎn)。

思路三：用hashMap數(shù)據(jù)結(jié)構(gòu)
第一個while循環(huán)遍歷第一個鏈表匙铡，將其所有節(jié)點(diǎn)放入hashmap中
第二個while遍歷第二個鏈表图甜，用containsKey判斷這個節(jié)點(diǎn)值是否存在第一個鏈表中。
（這種思路基本上就是用空間換時間）

思路四：兩個鏈表的公共節(jié)點(diǎn)一定在鏈表的尾部
若連個鏈表存在公共節(jié)點(diǎn)鳖眼，則它們的尾部一定從第一個公共節(jié)點(diǎn)開始完全相同黑毅。

我們分析有公共結(jié)點(diǎn)的兩個鏈表有哪些特點(diǎn)。從鏈表結(jié)點(diǎn)的定義可以看出钦讳，這兩個鏈表是單鏈表矿瘦。如果兩個單向鏈表有公共的結(jié)點(diǎn)，那么這兩個鏈表從某一結(jié)點(diǎn)開始愿卒，它們的next都指向同一個結(jié)點(diǎn)缚去，但由于是單向鏈表的結(jié)點(diǎn)，之后他們所有結(jié)點(diǎn)都是重合的掘猿，不可能再出現(xiàn)分叉病游。所以兩個有公共結(jié)點(diǎn)而部分重合的鏈表，拓?fù)湫螤铋_起來像一個Y稠通，而不可能像X衬衬。

兩個鏈表的公共節(jié)點(diǎn)圖解

解答：

思路二：長鏈表先走n步筏餐，然后長短鏈表共同向前遍歷

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
 if (pHead1 == null || pHead2 == null) return null;
        if (pHead1 == pHead2) return pHead1;
        int len1 = getLength(pHead1);
        int len2 = getLength(pHead2);
        //讓比較長的鏈表先走幾步
        if (len1 > len2) {
            for (int i = 0; i < (len1 - len2); i++) {
                pHead1 = pHead1.next;
            }
        } else {
            for (int i = 0; i < (len2 - len1); i++) {
                pHead2 = pHead2.next;
            }
        }
        boolean flag = false;  //標(biāo)志位开泽，判斷是否走到第一個公共節(jié)點(diǎn)
        ListNode result = null;
        while (!flag) {
            if (pHead1 == null || pHead2 == null) {
                return null;
            }
            if (pHead1.val == pHead2.val) {
                flag = true;
                result = pHead1;
            } else {
                pHead1 = pHead1.next;
                pHead2 = pHead2.next;
            }
        }
        return result;
    }

    /*求鏈表長度的方法，每次求鏈表漲肚魁瞪，需要遍歷一次單鏈表*/
    public static int getLength(ListNode pHead) {
        int len = 1;
        ListNode current = pHead;
        while (current.next != null) {
            len++;
            current = current.next;
        }
        return len;
    }
}

運(yùn)行成功

這種方法可行穆律，但是求鏈表的長度需要遍歷一次鏈表惠呼，然后找到公共節(jié)點(diǎn)又要遍歷兩個鏈表，時間復(fù)雜度是O(M+N),但是鑒于每個鏈表都要遍歷兩遍峦耘，所以耗時還是比較多的剔蹋。

如果想耗時比較少，可以考慮用空間換取時間辅髓，用hashmap存儲鏈表1中的節(jié)點(diǎn)值泣崩，然后遍歷一遍鏈表2即可。從hashmap中查找某個key值是否存在耗費(fèi)的時間為O（1）利朵。

思路四：當(dāng)指針1訪問到A的末尾開始訪問B律想，當(dāng)指針2訪問到B的末尾開始訪問A，這樣绍弟，指針1,2會同時訪問到公共節(jié)點(diǎn)技即。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
   public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode l1 = pHead1, l2 = pHead2;
        while (l1 != l2) {
            l1 = (l1 == null) ? pHead2 : l1.next;
            l2 = (l2 == null) ? pHead1 : l2.next;
        }
        return l1;
    }
}

運(yùn)行成功

簡潔高效的代碼是程序媛永恒的追求！