Intersection of two linked list

获得两条链表的连接点

 

my solution (36ms, 100%)

(虽然效率看起来是最好的, 但是其实比起最好的算法要差不少)

核心难点在于两条链表的长度不一定相等, 这样就不能遍历节点用等于的形式来判断

那么拿到两条链表的长度, 让较长的链表前进若干次, 以达到长度相等的情形, 那么就可以遍历了

代码如下, 会产生 3 次遍历, 两次完整的遍历 O(3n) => O(n)

 

the best solution

原来还可以这么做!!!

算法的核心思想在于, A + B = B + A

假设有两条链表, 长度不等

其中将他们的链接点标为 2

那么有以下组合链表

他们如果有链接点, 那么在第二次循环时必然相等

我是用求深度差来解决这个问题, 这个算法更加巧妙地用组合链表的形式规避了这个深度差