两个单向链表，有可能交叉，请设计算法判断是否交叉，如果交叉，

[问答题]

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

推荐

八公八母

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

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

编辑于 2015-02-09 09:47:14 回复(0)

JefferySaw

看到个大佬（selfboot）的题解，整理下逻辑思路发上来。

代码逻辑是让两个指针同时走两条链表，走完当前链表时继续走另一条链表，最终指针一定在第一个交叉点或NULL相遇。

根据图示：

1、当链表相交时，指针A、B分别需要走x+z+y+z和y+z+x+z，由于两个指针同时走，速度相同，所以指针必定在最后一段z的起始相遇。

2、当链表不相交时，指针A、B分别需要走x+y和y+x，由于两个指针同时走，速度相同，所以指针必定在最后的NULL相遇。

附上大佬的代码：

class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {
    	ListNode *p1 = pHead1;
        ListNode *p2 = pHead2;
        while(p1!=p2){
            p1 = (p1==NULL ? pHead2 : p1->next);
            p2 = (p2==NULL ? pHead1 : p2->next);
        }
        return p1;
    }
};

发表于 2021-08-18 09:25:51 回复(0)