我要招人

去企业版

首页 > 试题广场 >

两个链表的第一个公共结点

[编程题]两个链表的第一个公共结点

热度指数：689552 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

数据范围： $n \le 1000$
要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：

可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。

输入描述:

输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和第二个链表的公共部分。
后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面，用户得到的输入只有pHead1和pHead2。

输出描述:

返回传入的pHead1和pHead2的第一个公共结点，后台会打印以该节点为头节点的链表。

示例1

输入

{1,2,3},{4,5},{6,7}

输出

{6,7}

说明

第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分
这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的

示例2

输入

{1},{2,3},{}

输出

{}

说明

2个链表没有公共节点 ,返回null，后台打印{}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

LaN666

发表于 2021-06-21 23:39:51

精华题解 36、两个链表的第一个公共结点解题思路：使用两个指针N1,N2，一个从链表1的头节点开始遍历，我们记为N1，一个从链表2的头节点开始遍历，我们记为N2。让N1和N2一起遍历，当N1先走完链表1的尽头（为null）的时候，则从链表2的头节点继续遍历，同样，如果N2先走完了链表2的尽头，则从链表1 展开全文

Maokt

发表于 2021-07-15 11:20:58

精华题解算法思想一：双指针解题思路：使用两个指针 a，b 分别指向两个链表 pHead1，pHead2的头结点，然后同时分别逐结点遍历，当 a 到达链表 pHead1的末尾时，重新定位到链表 pHead2的头结点；当 b 到达链表 pHead2 的末尾时，重新定位到链表 pHead1的头结点展开全文

牛客313925129号

发表于 2021-07-15 16:17:29

精华题解方法一对于两个链表的问题，首先想到双指针的方法。在这道题中，两个链表长度不一定相等，不能直接使用双指针，我们需要在长链表上先移动一段距离，再进行比较。因为公共部分肯定在链表后面部分，所以不需要担心这一操作导致跳过了第一个公共结点。示意图如下：具体代码如下： /* struct ListNode { 展开全文

江南好___

发表于 2021-06-22 22:45:28

精华题解描述题目描述输入两个无环的单链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）示例输入：{1,2,3},{4,5},{6,7} 返回值：{6,7} 说明：第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{ 展开全文

NumPy

发表于 2021-06-22 17:39:17

精华题解一、题目描述 JZ36两个链表的第一个公共结点题目大意：给定两个链表A和B,他们尾部的几个结点可能是相同的,我们需要返回第一个公共结点的指针注意审题：两个链表也可以没有公共结点,此时返回空指针即可二、算法1（双指针）算法思路 1.总体思路：我们可以分别用两个指针指向链表的头结点,然后一步一步地向展开全文

牛客题解官

发表于 2020-06-01 14:52:58

描述这是一篇针对初学者的题解知识点：单链表难度：一星题解题目抽象：给定两个单链表A，B，假设一定含有公共结点，返回第一个公共结点的指针。方法：双指针法假如例子如下：显然第一个公共结点为8，但是链表A头结点到8的长度为2，链表B头结点到8的长度为3，显然不好办？如果我们能够制造一种理想情况展开全文

一叶浮尘

发表于 2019-08-21 08:53:04

输入两个链表，找出它们的第一个公共结点。按照自己以往的思路肯定第一反应用HashSet和HashMap就能很快解决此问题，但是如果真的面试出了这道题目肯定不是面试官想要的思路。有一种简单的解调思路：那就是遍历两遍这两个链表，如果有重复的节点，那么一定能够使遍历的指针相等。链接：https:/ 展开全文

郭家兴0624

发表于 2019-08-11 20:16:39

题目描述输入两个链表，找出它们的第一个公共结点。思路：首先我们要知道什么是公共节点，两个链表从某一节点开始，他们的next都指向同一个节点。但由于是单向链表的节点，每个节点只有一个next，因此从第一个公共节点开始，之后他们的所有节点都是重合的，不可能再出现分叉。所以可以先遍历两个链表得到他们的长展开全文

宫水三叶的刷题日记

发表于 2021-07-26 15:32:45

朴素解法一个朴素的解法自然是两层枚举，逐个检查哪个节点相同。代码： public class Solution { public ListNode FindFirstCommonNode(ListNode a, ListNode b) { for (ListNode h1 展开全文

不是江小白

发表于 2021-07-27 20:37:09

1. 常规思路既然题目已经明知是两个无环的单链表，那么此题难度就降低了。常规思路就是用一个哈希集合来存储第一个链表遍历后的所有节点；接着遍历第二个链表，与哈希集合中的节点进行比较：如果第二个链表中节点不存在于哈希集合中，那么移动到下一个节点再比较；否则，节点存在于哈希集合中，返回第二个链表的展开全文

Cyril-廖思睿

发表于 2020-01-06 20:17:08

题目中没有说有环还是无环，所以有了下面一大堆长的代码。思路在注释中。 public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { // 处理空的情况展开全文

vorking

发表于 2020-03-27 13:39:14

总结一下，三种解法（C++实现）： //////////////////////////////////////////// ①stack解法：两个链表先分别进栈再依次出栈，从后向前遍历遇到第一个不相等的节点返回上一个相同节点即可 //////////// 展开全文

大型设备

发表于 2022-01-02 13:37:27

#被大佬教了一个特别惊艳的方法# 我们摸索着向前，盼望着相见，可或许你的路要更长，让我们遗憾地在交叉路口擦肩而过，无妨，当我们各自走过尽头，请回到对方最初的起点，重温对方的路，我们终会在交叉路口，紧紧相拥。我多想在终点等你，可谁让这道题非要我们相遇在交叉路口才行呢 # def __init 展开全文

摸鱼学大师

发表于 2021-10-02 20:26:18

题目的主要信息：两个无环的单向链表，找出它们的第一个公共结点如果没有公共节点则返回空要求：空间复杂度O(1)O(1)O(1)，时间复杂度O(n)O(n)O(n) 方法一：长度比较法具体做法：我们可以分别统计两个链表的长度，然后对于较长的一个链表先走长度之差这么多步，在同步往后遍历，遇到展开全文

猪客

发表于 2019-10-01 15:10:12

#java 对 @一叶浮沉(3839111) 代码思路的理解+分析ps:第一眼看去差点没看明白跑了下是对的然后加入了些分析希望对别人有帮助吧! public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHe 展开全文

问题信息

链表

难度：

1432条回答 2425收藏 128050浏览

通过挑战的用户

查看代码

少糖加蛋娃哈哈

2023-03-14 10:58:05
牛客20133...

2023-03-10 16:30:41
牛客17038...

2023-03-09 17:20:34
K乀

2023-02-27 22:56:47
GeekExp...

2023-02-16 14:00:55