描述

輸入兩個無環(huán)的單向鏈表，找出它們的第一個公共結(jié)點，如果沒有公共節(jié)點則返回空。（注意因為傳入數(shù)據(jù)是鏈表，所以錯誤測試數(shù)據(jù)的提示是用其他方式顯示的，保證傳入數(shù)據(jù)是正確的）

數(shù)據(jù)范圍： n≤1000
要求：空間復雜度 O(1)，時間復雜度 O(n)

例如，輸入{1,2,3},{4,5},{6,7}時，兩個無環(huán)的單向鏈表的結(jié)構(gòu)如下圖所示：

鏈表公共結(jié)點示例.png

可以看到它們的第一個公共結(jié)點的結(jié)點值為6，所以返回結(jié)點值為6的結(jié)點。

輸入描述：

輸入分為是3段，第一段是第一個鏈表的非公共部分，第二段是第二個鏈表的非公共部分，第三段是第一個鏈表和第二個鏈表的公共部分。 后臺會將這3個參數(shù)組裝為兩個鏈表，并將這兩個鏈表對應的頭節(jié)點傳入到函數(shù)FindFirstCommonNode里面，用戶得到的輸入只有pHead1和pHead2。

返回值描述：

返回傳入的pHead1和pHead2的第一個公共結(jié)點，后臺會打印以該節(jié)點為頭節(jié)點的鏈表。

示例1

輸入：{1,2,3},{4,5},{6,7}
返回值：{6,7}
說明：第一個參數(shù){1,2,3}代表是第一個鏈表非公共部分，第二個參數(shù){4,5}代表是第二個鏈表非公共部分，最后的{6,7}表示的是2個鏈表的公共部分，這3個參數(shù)最后在后臺會組裝成為2個兩個無環(huán)的單鏈表，且是有公共節(jié)點的

示例2

輸入：{1},{2,3},{}
返回值：{}
說明：2個鏈表沒有公共節(jié)點 ,返回null，后臺打印{}

解題思路：pHead1->pHead2 pHead2->pHead1

1、定義兩個ListNode節(jié)點，分別指向pHead1,pHead2;
2、while循環(huán)條件的結(jié)束條件是first和second相等，包括空；
3、兩個結(jié)點同時向前走，每個節(jié)點先走當前鏈表的每個節(jié)點，再去走另外鏈表的每個的節(jié)點，當first走到末尾時，走pHead2,second走到末尾時走pHead1
3、若有公共結(jié)點，跳出while循環(huán)，若沒有公共結(jié)點，走到first和second都為空時，也會結(jié)束while循環(huán)。

代碼實現(xiàn):
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode first = pHead1;
        ListNode second = pHead2;
        while(first != second){
            if(first == null){
                 first = pHead2;
             }else{
                first = first.next;
            }
             if(second == null){
                 second = pHead1;
             }else{
                 second = second.next;
             }
        }
        return first;
    }