# 160 intersection of two linked lists

### 160. Intersection of Two Linked Lists

Easy

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


AC代码如下:

class Solution(object):
"""
:rtype: ListNode
"""
while pA is not pB:
pA = pA.next if pA else headB
pB = pB.next 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

apachecn/AiLearning