160 intersection of two linked lists
160. Intersection of Two Linked Lists
题目: https://leetcode.com/problems/intersection-of-two-linked-lists/
难度:
Easy
如果两个linkedlist有intersection的话，可以看到，其实如果一开始我们就走到b2的话，那么我们就可以两个pointer一个一个的对比，到哪一个地址一样，接下来就是intersection部分。
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
比较巧妙的数学解法，看下面的解释和代码
AC代码如下:
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
pA, pB = headA, headB
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
