如何判断两个链表是否相交

如何判断两个链表是否相交

O(): 两层遍历，总能发现是否相交

O(n): 一层遍历，遍历完两个链表，如果两个链表的最后一个结点指针相同，则相交，否则不相交

问题描述
问题一: 如何判断一个链表是否有环,如果有, 则返回第一个进入环的节点, 没有则返回null.
问题二: 如何判断两个无环链表是否相交, 相交则返回第一个相交节点, 不相交则返回null.
问题三: 如何判断两个有环链表是否相交, 相交则返回第一个相交节点, 不相交则返回null.

问题一

问题一: 如何判断一个链表是否有环,如果有, 则返回第一个进入环的节点, 没有则返回null.

算法:

1. 设置两个指针 pLow, pFast, 都从第一个节点出发
2. pLow每次前进一个节点
3. pFast每次前进两个节点
4. 如果pFast遇到了null 节点, 则说明链表无环, 返回null
5. 如果pLow和pFast相遇, 则说明链表有环
6. 确定第一个进入环的节点:
   • 记从头节点到入环节点的距离为x
   • 入环节点到pLow和pFast相遇节点的距离为y
   • pLow到相遇节点走过的距离为s, 则由 s = x + y
   • 记环的长度为r, 则pFast到相遇时走过的距离为 s + nr, n >= 1
   • 因为pFast走过的距离为pLow的两倍, 则有s + nr = 2s
   • 则可推出 s = nr -> x + y = nr -> x = nr - y
   • 由以上公式可得到, 当一个指针p1从头节点触发, 一个指针p2从相交节点出发, p1走过x的距离时, p2走过nr - y的距离, 又因为p2离相交点的距离为y(此处可画图理解), 所以当p1与p2相遇时, 必然在相交点处.

问题二:

问题二: 如何判断两个无环链表是否相交, 相交则返回第一个相交节点, 不相交则返回null.

算法:

1. 得到链表1和链表2的长度, 分别记为 len1, len2, 假设 len1 > len2
2. p1指向链表1的头节点, p2指向链表2的头节点
3. p1先移动 len1 - len2的距离
4. 之后p1和p2同时移动, 并比较两个指针指向的节点是否相同, 如果相同,则说明两个链表相交, 返回该节点. 如果不相同, 继续移动, 直到链表结尾, 说明两个链表不相交.

问题三:

问题三: 如何判断两个有环链表是否相交, 相交则返回第一个相交节点, 不相交则返回null.

算法:
分为三种情况

1. 先根据问题一的算法, 找到两个有环链表的入环节点.
2. case 1: 如果两个链表的入环节点相同, 则两个链表相交
   • 入环节点作为尾部节点, 转换为问题二.

情况一

1. 如果两个链表的入环节点不同

* case 2: 固定一个入环节点, 从另一个入环节点出发, 遍历环一周, 如果遇到第一个入环节点, 则两个链表相交, 返回任意一个入环节点即可.

情况二

 * case 3: 如果遍历环一周, 没有遇到第一个入环节点, 则两个链表不相交.

情况三