兩個連結清單的第一個公共結點（思路與實作）

題目描述

輸入兩個連結清單，找出它們的第一個公共結點

思路：

兩個連結清單找到公共的結點，可以肯定的是公共結點後面的結點都是相同的，那麼現在就出現兩種情況，一種情況是兩個連結清單的長處相等，此時同時周遊這兩個連結清單就可以找到。另外一種情況則是兩個連結清單的長度不一樣，此時就第一步就需要解決這個長度差，是以可以先得到兩個連結清單的長度，将長的連結清單移動長度差。然後兩個連結清單再同時走（原因是兩個連結清單隻能是不是公共區才會造成連結清單不一樣長）。

第一種實作：

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        int len1 = findLen(pHead1);
        int len2 = findLen(pHead2);
        if(len1 < len2){
            for(int j = 0; j < len2 - len1; j ++){
                pHead2 = pHead2.next;
            }
            while(pHead1 != pHead2){
                pHead1 = pHead1.next;
                pHead2 = pHead2.next;
            }
            return pHead1;
        }else if(len1 > len2){
            for(int j = 0; j < len1 - len2; j ++){
                pHead1 = pHead1.next;
            }
            while(pHead1 != pHead2){
                pHead1 = pHead1.next;
                pHead2 = pHead2.next;
            }
            return pHead1;
        }else{
            while(pHead1 != pHead2){
                pHead1 = pHead1.next;
                pHead2 = pHead2.next;
            }
            return pHead1;
        }
    }
    public static int findLen(ListNode node){
        int i = 0;
        while(node != null){
            node = node.next;
            i ++;
        }
        return i;
    }
}
           

第二種實作：

/*
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 p1 = pHead1;
        ListNode p2 = pHead2;
        
        while(p1 != p2){//如果這兩個連結清單的長度一樣，那麼就同步。如果長度不一樣，那麼樣能第一圈解決這個距離差
            p1 = (p1 == null? pHead2 : p1.next);
            p2 = (p2 == null? pHead1 : p2.next);
        }
        return p1;
    }
}