C***y 发帖数: 2546 | 1 两个singly linked list, 问如何判断是否相交,相交的话找出第一个相交的节点
变种:找binary tree中两个node 的lowest common ancestor,node有一个parent指针 | g*********e 发帖数: 14401 | 2 my solution for 1:
if they intersect, they would end up in the same node, so just traverse to
the end and see if the two end node is the same.
If the same, then we can connect the end node to the start of the second
list( making it a circular list), then set two pointers from the start of
the first list, going at speed of 1 and 2 node per time. their first meet
would be the same distance from the intersect as the start position. | g*********e 发帖数: 14401 | 3 pro 2 is easy,
you just find the depth difference of the two nodes.
then proceed the node at lower level up to make them at the same level,
then check and go up together. |
|