茉莉Python

voidqueens@hotmail.com

0%

数据结构与算法-15-链表

扩展:链表有环,如何判断相交?

分析:如果有环且两个链表相交,则两个链表都有共同一个环,即环上的任意一个节点都存在于两个链表上。因此,就可以判断一链表上俩指针相遇的那个节点,在不在另一条链表上。

无环链表和有环链表是不可能相交的;

两个有环链表若相交,其“整个环上”的所有node一定都重合;

有环链表的相交,情况只有2种:相交于”环上”或相交于”不是环的部分”,即下图所示;

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/link.png

1
https://cloud.tencent.com/developer/article/1045468