BM10 两个链表的第一个公共结点
想法1:两个指针到达两个链表末尾,然后不断向前直到不相同的结点,缺点:单向链表做不到向前
想法2:暴力法,比较两个链表两两成对的地址是否一致,Python可以比较id,缺点:复杂度为O(n^2)
想法3:改进想法1,使用栈存储遍历过的节点,不断出栈,缺点:空间复杂度为O(n)
双指针法:
想法4:参照题解,遍历完链表后从另一个链表继续遍历,直到两个指针相遇,缺点:难想到;两个链表长度不同时,无法第一次就在共同部分的同一位置遇见;当长度相同时,速度极快,且最优
想法5:先计算长度差,再领先长度差遍历直到遇见
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Min的博客!
评论