劍指offer-兩個連結清單的第一個公共結點

題目描述

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

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
           

思路

有公共結點的連結清單的特點：兩個連結清單從某一結點開始，他們的next指向同一個結點。

當兩個連結清單長度不同時，如果從頭周遊到尾結點時間不一緻。

是以首先第一次周遊兩個連結清單得到各自的長度，可知哪個連結清單長，以及長多少（比如為lenDif）。

第二次周遊，在較長的連結清單先走lenDif，然後同時周遊兩個連結清單，找到的第一個相同的結點就是第一個公共結點。

java實作

/*
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;
        //計算兩個連結清單的長度
        int len1=GetListLength(pHead1);
        int len2=GetListLength(pHead2);
        int lenDif=0;
        ListNode pLong=null;
        ListNode pShort=null;
        //設定長短連結清單的頭指針，以及長度差lenDif
        if(len1>len2){
            lenDif=len1-len2;
            pLong=pHead1;
            pShort=pHead2;
        }
        else{
            lenDif=len2-len1;
            pLong=pHead2;
            pShort=pHead1;
        }
        //長連結清單先走lenDif步，使得剩下的長度一樣
        for(int i=0;i<lenDif;i++){
            pLong=pLong.next;
        }
        //此時剩下的長度一樣，同時周遊
        while (pLong!=null && pShort!=null && pLong!=pShort){
            pLong=pLong.next;
            pShort=pShort.next;
        }
        return pLong;
    }

    int GetListLength(ListNode pHead){
        int length=0;
        while (pHead.next!=null){
            length++;
            pHead=pHead.next;
        }
        return length;
    }
}