[LC 160]. Intersection of Two Linked Lists

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

A,B是可能不同长度,因此不能同时到达C1,聪明的做法是让两个list都同时循环lenA+lenB-lenC个node,lenC是重合部分长度。所以对A,当循环到队尾null时,继续走到headB,同样对B当循环到队尾null时,继续走到headA,这样到达C1的时间就相同了。当然用求两个队列差值的方法,two pass也可以做到O(n) time 和 O(1) space。


public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode a = headA;
    ListNode b = headB;

    while (a != b) {
        a = (a == null) ? headB : a.next;
        b = (b == null) ? headA : b.next;
    }

    return a;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s