找到两个单向链表的第一个公共节点

时间:2021-05-31 11:05:10
如果两个单向链表有公共节点,则两个链表会构成Y型结构,最后一个节点相同。

我们可以从头开始遍历两个链表,找到最后一个节点的指针,设为p_a,p_b。同时记录下两个链表的长度len_a,len_b(假设len_a >= len_b)。
如果p_a == p_b,则说明两个链表有公共节点,否则没有。
如果有公共节点,则第一个公共节点距起始节点的距离满足 len_a - start_a == len_b - start_b。
所以第一个可能的公共节点距起始节点的距离是 len_a - len_b, 0。我们从这两个节点开始比较,直到找到第一个公共节点。