【剑指offer52】两个链表的第一个公共节点

English description is not available for the problem. Please switch to Chinese.

切换英文的时候看到了这个提示&＃xff0c;这题居然没有英文形式…好吧,不过以后我要把题目的图片用md语法UML图画出来&＃xff0c;然后也会更新动图详解&＃xff0c;不过现在太忙了&＃xff0c;所以先这样吧&＃xff0c;先把题解数量多起来&＃xff0c;再考虑题解的内容丰富起来吧&＃xff0c;同时我本来打算用多门语言&＃xff08;c/c&＃43;&＃43;/java/python/Javascript/golang&＃xff09;解答的&＃xff0c;奈何太菜了。实验了一段时间后发现自己做不到融会贯通&＃xff0c;反而使文章变得臃肿。所以打算暂时放弃&＃xff0c;由于目前学校正在学C&＃xff0c;所以暂时所有题目暂用C解答

题目描述

输入两个链表&＃xff0c;找出它们的第一个公共节点。
如下面的两个链表&＃xff1a;

在节点 c1 开始相交。
示例 1&＃xff1a;

输入&＃xff1a;intersectVal &＃61; 8, listA &＃61; [4,1,8,4,5], listB &＃61; [5,0,1,8,4,5], skipA &＃61; 2, skipB &＃61; 3
输出&＃xff1a;Reference of the node with value &＃61; 8
输入解释&＃xff1a;相交节点的值为 8 &＃xff08;注意&＃xff0c;如果两个列表相交则不能为 0&＃xff09;。从各自的表头开始算起&＃xff0c;链表 A 为 [4,1,8,4,5]&＃xff0c;链表 B 为 [5,0,1,8,4,5]。在 A 中&＃xff0c;相交节点前有 2 个节点&＃xff1b;在 B 中&＃xff0c;相交节点前有 3 个节点。


示例 2&＃xff1a;

输入&＃xff1a;intersectVal &＃61; 2, listA &＃61; [0,9,1,2,4], listB &＃61; [3,2,4], skipA &＃61; 3, skipB &＃61; 1
输出&＃xff1a;Reference of the node with value &＃61; 2
输入解释&＃xff1a;相交节点的值为 2 &＃xff08;注意&＃xff0c;如果两个列表相交则不能为 0&＃xff09;。从各自的表头开始算起&＃xff0c;链表 A 为 [0,9,1,2,4]&＃xff0c;链表 B 为 [3,2,4]。在 A 中&＃xff0c;相交节点前有 3 个节点&＃xff1b;在 B 中&＃xff0c;相交节点前有 1 个节点。


示例 3&＃xff1a;

输入&＃xff1a;intersectVal &＃61; 0, listA &＃61; [2,6,4], listB &＃61; [1,5], skipA &＃61; 3, skipB &＃61; 2
输出&＃xff1a;null
输入解释&＃xff1a;从各自的表头开始算起&＃xff0c;链表 A 为 [2,6,4]&＃xff0c;链表 B 为 [1,5]。由于这两个链表不相交&＃xff0c;所以 intersectVal 必须为 0&＃xff0c;而 skipA 和 skipB 可以是任意值。
解释&＃xff1a;这两个链表不相交&＃xff0c;因此返回 null。


注意&＃xff1a;

• 如果两个链表没有交点&＃xff0c;返回 null.
• 在返回结果后&＃xff0c;两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 $O(n)$ 时间复杂度&＃xff0c;且仅用 $O(1)$ 内存。

相关标签

哈希表&＃xff0c;链表&＃xff0c;双指针

题解正文

哈希表