存在交点的两条(不存在环)链表,其尾部节点一定是相同的(这里有些朋友可能会有疑问,相交的链表不能是蝶形的吗(这样两条链表就可能存在不相同的尾部节点)?...其实对于相交的链表来说,是不可能存在蝶形的相交方式的,因为对于相交的那个链表节点来说,其只有一个链接指针,不能形成蝶形链接),所以我们直接遍历两条链表至尾部,然后比较各自的尾部节点是否相同就可以了~
至于如何找出链表相交的交点...方法同样需要技巧性:
首先我们要计算出链表中环的元素个数,方法就是扩展使用上述判断链表有环的方法: 当慢指针和快指针相遇时(此时可以判断链表一定有环),那么相遇的那个链表节点就一定是环中的某一节点,我们从这个节点出发遍历链表...得到了链表中环的元素个数,我们便可以尝试找出入环点了:
我们创建两个指针,并让其中一个指针首先步进 lcl_clc 个节点,之后再让两个指针同步遍历,当两个指针相遇时,其共同指向的那个链表节点即为链表的入环点...首先要说明下什么是数组的主元素,所谓数组的主元素,是指出现次数大于 n/2n / 2n/2 (nnn 为数组的元素个数)的数组元素,例如数组 [2,1,1,1][2, 1, 1, 1][2,1,1,1]