问答题 18 /71

两个单向链表，有可能交叉，请设计算法判断是否交叉，如果交叉，返回交叉点！算法复杂度o(n)

参考答案

两个链表最后是合并成一个而不是交叉所以：
（1）先找到p1，p2的最后一个节点，同时记录节点数量a，b；
（2）判断最后一个节点是否相同，

如果不相同则没相交。
如果相同则从第一个节点和|a-b|+1个节点开始比较看是否相等不相等都寻找下一个节点
直到找到交叉点

查看讨论

上一题下一题

扫一扫，把题目装进口袋