求自定义两个单链表相交首节点查找方法的时间与空间复杂度

时间复杂度 #

这段代码通过两层嵌套循环检查链表节点是否相交：

• 外层循环遍历第一个链表的所有节点，假设第一个链表长度为 m

• 外层每遍历一个节点，内层循环就会完整遍历第二个链表的所有节点，假设第二个链表长度为 n

• 最好情况：两个链表的首个节点就相交，仅需1次比较即可返回结果，时间复杂度为 O(1)

• 最坏情况：两个链表不相交，或相交节点位于两个链表的末尾，此时需要遍历所有节点组合，时间复杂度为 O(m*n)

综上，该方法的时间复杂度为 O(mn)（m、n分别为两个单链表的长度）。

空间复杂度 #

代码执行过程中仅使用了currentPtr1、currentPtr2、firstNode这几个固定数量的指针变量，没有开辟与链表长度相关的额外存储空间，空间开销始终恒定。

因此，该方法的空间复杂度为 O(1)。

内容的提问来源于stack exchange，提问作者programmer0x06