Skip to content

160 intersection of two linked lists

160. Intersection of Two Linked Lists





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



class Solution(object):
    def getIntersectionNode(self, headA, headB):
        :type head1, head1: ListNode
        :rtype: ListNode
        pA, pB = headA, headB
        while pA is not pB:
            pA = if pA else headB
            pB = if pB else headA
        return pA

Just count the number of moves by each pointer before they meet. One pointer will traverse entire list1 for N moves and then jump to the head of list1 to move (M-K) steps to intersection, where K represents the length of common part. Now the other pointer must also moved the same number of steps since they are both moved at the same time. The second pointer traverses the entire list2 for M steps and jumped to the head of list1 to move (N-K) steps. So the loop finished with M+N-K times. 详见zzg_zzm的评论

This algorithm is sooooo perfect!

I was wonder if the running time is O(n+m), but later I figured out that the actually running time is just:

  • m+n for non-intersection case

With intersection:

  • Suppose for LL-A, it’s a+b=n, a is the # of nodes before intersection

  • Suppose for LL-B, it’s c+b=m, c is the # of nodes before intersection

Thus the actual running time is a+b+c = n+c = m+a.

Actually, when b=0, this just stands for the case with no intersection with a+b+c=n+m