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

本文首發于我的個人部落格： 尾尾部落

題目描述

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

解題思路

如果兩個連結清單存在公共結點，那麼它們從公共結點開始一直到連結清單的結尾都是一樣的，是以我們隻需要從連結清單的結尾開始，往前搜尋，找到最後一個相同的結點即可。但是題目給出的單向連結清單，我們隻能從前向後搜尋，這時，我們就可以借助棧來完成。先把兩個連結清單依次裝到兩個棧中，然後比較兩個棧的棧頂結點是否相同，如果相同則出棧，如果不同，那最後相同的結點就是我們要的傳回值。

還有一種方法，不需要借助棧。先找出2個連結清單的長度，然後讓長的先走兩個連結清單的長度差，然後再一起走，直到找到第一個公共結點。

參考代碼

法1：

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

    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.Stack;
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        Stack<ListNode> s1 = new Stack<>();
        Stack<ListNode> s2 = new Stack<>();
        while(pHead1 != null){
            s1.push(pHead1);
            pHead1 = pHead1.next;
        }
        while(pHead2 != null){
            s2.push(pHead2);
            pHead2 = pHead2.next;
        }
        
        ListNode res = null;
        while(!s1.isEmpty() && !s2.isEmpty() && s1.peek() == s2.peek()){
            s1.pop();
            res = s2.pop();
        }
        return res;
    }
}
           

法2：

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == null || pHead2 == null)
            return null;
        int count1 = 1, count2 = 1;
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while(p1.next != null){
            p1 = p1.next;
            count1++;
        }
        while(p2.next != null){
            p2 = p2.next;
            count2++;
        }
        if(count1>count2){
            int dif = count1 - count2;
            while(dif != 0){
                pHead1 = pHead1.next;
                dif--;
            }
        }else{
            int dif = count2 - count1;
            while(dif != 0){
                pHead2 = pHead2.next;
                dif--;
            }
        }
        while(pHead1 != null && pHead2 != null){
            if(pHead1 == pHead2)
                return pHead1;
            pHead1 = pHead1.next;
            pHead2 = pHead2.next;
        }
        return null;
    }
}