LeetCode Intersection of Two Linked Lists 解題報告

LeetCode Intersection of Two Linked Lists 解題報告

 
求兩個鏈表的第一個公共節點，如果不存在公共節點的話就返回null。

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

解題思路：
1）如果兩個鏈表的最後一個節點一樣，那麼說明兩個鏈表一定有交點。
2）分別求出兩個鏈表的長度，然後對長度長的鏈表向前移動：LengA - LengB，將兩個鏈表進行對齊，之後一起遍歷，直到找到第一個相同的節點。

public class Solution {
    
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null) {
            return null;
        }
        int lengthA = 1;
        int lengthB = 1;
        
        ListNode iterA = headA;
        while(iterA.next!=null) {
            iterA = iterA.next;
            lengthA++;
        }
        
        ListNode iterB = headB;
        while(iterB.next!=null) {
            iterB = iterB.next;
            lengthB++;
        }
        
        if(iterA!=iterB) {
            return null;
        }
        
        if(lengthA>lengthB) {
            int tmp = lengthA - lengthB;
            while(tmp>0) {
                headA = headA.next;
                tmp--;
            }
        } else {
            int tmp = lengthB - lengthA;
            while(tmp>0) {
                headB = headB.next;
                tmp--;
            }
        }
        
        
        
        
        while(headA!=headB) {
            headA = headA.next;
            headB = headB.next;
        }
        
        return headA;
    }
}