兩個單向連結清單的第一個公共結點

leetcode160：相交連結清單

題目：

編寫一個程式，找到兩個單連結清單相交的起始節點

執行個體：

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3
           

思路：

因為連結清單是單向連結清單，是以相交連結清單的形狀就像倒置的 Y，這就有個==特點==：相交點之後的結點都相同。是以找到第一個相同的結點就是連結清單的第一個公共結點。

如果正向周遊連結清單，因為連結清單的長度不相同，是以無法通過的時間使他們的步伐統一。解決辦法是首先比較連結清單兩個的長度，然後讓較長的連結清單的先走他們長度的內插補點，然後同一步伐一起走，知道走到的結點相同時，就找的了第一個公共結點。

時間複雜度分析：空間複雜度O（1），時間複雜度O(n)

運作時間：2ms

//計算連結清單的長度
private int calculateNodes(ListNode head){
    int val=;
    for(;head!=null;head=head.next)
        val++;
    return val;
}
//循環周遊，需要借助于棧
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if(headA==null || headB==null)
        return null;
    //用來儲存連結清單之間的內插補點
    int temp=;
    ListNode res=null;

    //計算兩個連結清單的長度，較長的連結清單先走幾步
    int lenA=calculateNodes(headA);
    int lenB=calculateNodes(headB);
    if(lenA>lenB){
        temp=lenA-lenB;
        for(int i=;i<temp;i++)
          headA=headA.next;
    }
    else{
        temp=lenB-lenA;
        for(int i=;i<temp;i++)
            headB=headB.next;
    }

    //兩個連結清單同步走，當腳下節點相同時，就找到了
    for(;headA!=null && headB!=null;headA=headA.next,headB=headB.next){
        if(headA==headB){
            res=headA;
            break;
        }

    }
    return res;
}
           

如果從後面周遊連結清單，因為結點都相同，是以第一個不相同的結點就是他們第一個公共結點。但是連結清單隻能從頭開始周遊，但卻要從後面開始比較，可以利用棧結構。使用兩個棧，分别從頭開始周遊兩個連結清單，然後出棧，如果棧頂元素不相同，那麼剛出棧的元素就是第一個公共結點。

時間複雜度分析：空間複雜度O(M+n),時間複雜度O(m+n)

運作時間：17ms

//使用兩個棧存儲空間
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
         if(headA==null ||  headB==null)
            return null;

        Stack<ListNode> list1 = new Stack<>();
        Stack<ListNode> list2 = new Stack<>();
        //儲存出棧結點
        ListNode temp=null;

        //向兩個棧中添加結點
        while(headA!=null){
            list1.add(headA);
            headA=headA.next;
        }
        while(headB!=null){
            list2.add(headB);
            headB=headB.next;
        }

        //比較，出棧
        while(!list1.isEmpty() && !list2.isEmpty() ){
            if(list1.peek() == list2.peek()){
                temp=list1.pop();
                list2.pop();
            }else
                break;
        }
        return temp;
}