这道题算是一个相遇问题:
假设有两个list, 它们之间也许有重叠的地方也许没有。 If there's intersect, Find begining node of the intersected list.
这道题自己做的时候犯了一个超级sb的错误。。就不分享我的idea了。。。
Leetcode上看到的一个解法:
while(a != b)
b=b==null? headA: b.next;
a=a==null? headB : a.next;
return a;
也就是每一次移动都先判断一下A同学和B同学是不是不在一个位置。如果俩人跑到同一个位置上的话, 那么就表示找到了Intersection Node。
A同学跑到终点以后,从B的赛道从头开始跑,B也有可能会切换到A的赛道。
对于两个完全没有联系的list的情况:
a-b-c-d-e-null
f-g-k-null
这个解法吊炸天的地方在于,它发现了当两个List长度不一样的时候,这个while 会停止after second iteration.
假设上述的两个完全没联系的lists, 第一次iteration时候, B到了null的时候,A还在赶路。
然后B跑到了A的跑道起点。由于两个List跑道是不一样长的,所以他们之间有一个固定的长度差。 比如跑道一 10步到终点,跑道二 6步到终点, 距离差为4。那么小明跑完从跑道二的时候小王在跑道一跑了6步,还差4步到终点。小明切换到赛道一,跑了4步的时候,小王跑到了终点,然后去了赛道二的起点。小明过了6步到底终点,小王刚好从赛道二也到了终点。
所以 等B在A的跑道上跑到终点的时候,A也在B的跑道上跑到了终点。两个人都在Null上面, a==b, break。