首页 > 试题广场 >

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

[编程题]两个链表的第一个公共结点
  • 热度指数：689634 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

数据范围：
要求：空间复杂度 ，时间复杂度

例如，输入{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，点此查看相关信息
算法知识视频讲解
添加回答
推荐
lizo头像 lizo 
/*
找出2个链表的长度，然后让长的先走两个链表的长度差，然后再一起走
（因为2个链表用公共的尾部）
*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) {
        int len1 = findListLenth(pHead1);
        int len2 = findListLenth(pHead2);
        if(len1 > len2){
            pHead1 = walkStep(pHead1,len1 - len2);
        }else{
            pHead2 = walkStep(pHead2,len2 - len1);
        }
        while(pHead1 != NULL){
            if(pHead1 == pHead2) return pHead1;
            pHead1 = pHead1->next;
            pHead2 = pHead2->next;
        }
        return NULL;
    }
    
    int findListLenth(ListNode *pHead1){
        if(pHead1 == NULL) return 0;
        int sum = 1;
        while(pHead1 = pHead1->next) sum++;
        return sum;
    }
    
    ListNode* walkStep(ListNode *pHead1, int step){
        while(step--){
            pHead1 = pHead1->next;
        }
        return pHead1;
    }
};

编辑于 2015-08-18 23:31:25 回复(82)
Javascript
折原修哉哉哉头像 折原修哉哉哉
用了Set写的，应该比较易懂 
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function FindFirstCommonNode(pHead1, pHead2)
{
    // write code here
    let set1 = new Set();
    while(pHead1){
        set1.add(pHead1);
        pHead1 = pHead1.next;
    }
    while(pHead2){
        if(set1.has(pHead2)){
            return pHead2;
        }
        pHead2 = pHead2.next;
    }
    return null;
}
module.exports = {
    FindFirstCommonNode : FindFirstCommonNode
};


发表于 2022-06-30 12:00:03 回复(0)
Javascript
funny_soul头像 funny_soul 
function FindFirstCommonNode(pHead1, pHead2)
{
    let cur1 = pHead1
    let cur2 = pHead2
    let myset = new Set()
    while(cur1!==null){
        if(!myset.has(cur1)){
            myset.add(cur1)
            cur1 = cur1.next
        }else{
            return cur1
        }
    }
    while(cur2!==null){
        if(!myset.has(cur2)){
            myset.add(cur2)
            cur2 = cur2.next
        }else{
            return cur2
        }
    }
    return null
}
使用集合做的巧妙解法
发表于 2022-05-20 10:48:39 回复(0)
Javascript
nicole27头像 nicole27 
function FindFirstCommonNode(pHead1, pHead2)
{
    // write code here
    let ta = pHead1;
    let tb = pHead2;
    while(ta!==tb){
        ta= (ta!==null?ta = ta.next:pHead2);
        tb= (tb!==null?tb = tb.next:pHead1);
    }
    return ta;
    
}

发表于 2022-03-04 13:15:19 回复(0)
Javascript
Elegy201905242021282头像 Elegy201905242021282
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function FindFirstCommonNode(pHead1, pHead2)
{
    // write code here
    let pLen1 = LinkTableLen(pHead1)
    let pLen2 = LinkTableLen(pHead2)
    let interval,lang,short
    if(pLen1 > pLen2) {
        lang = pHead1
        short = pHead2
        interval = pLen1 - pLen2
    } else {
        lang = pHead2
        short = pHead1
        interval = pLen2 - pLen1
    }
    while(interval--) {
        lang = lang.next
    }
    while(lang) {
        if(lang === short) {
            return lang
        }
        lang = lang.next
        short = short.next
    }
     return null
    
}
function LinkTableLen(node) {
    if(!node) {
        return 0
    }
    let index = 1
    while(node.next) {
        index++
        node = node.next
    }
    return index
}
module.exports = {
    FindFirstCommonNode : FindFirstCommonNode
};
发表于 2021-12-07 14:38:52 回复(0)
Javascript
takeheart莹头像 takeheart莹
// 利用set的不重复特性
function FindFirstCommonNode(pHead1, pHead2)
{
    if (!pHead1 || !pHead2) return null
    let set = new Set()
    while (pHead1) { // 先装上第一个链表的数据【为了防止本身的节点值重复】
        set.add(pHead1)
        pHead1 = pHead1.next
    }
    let oldLen = 0
    let oldVal = null
    while (pHead2) {
        oldLen = set.size
        set.add(pHead2)
        
        if (oldVal !== pHead2.val && oldLen + 1 !== set.size) { // 公共节点
            return pHead2
        }
        oldVal = pHead2.val // 先记录pHead2的值，防止pHead2本身的重复
        pHead2 = pHead2.next
    }
    return null
}
发表于 2021-10-07 09:42:54 回复(1)
Javascript
小夏不饿头像 小夏不饿 
function FindFirstCommonNode(pHead1, pHead2){
    let p1 = pHead1;
    let p2 = pHead2;
//     p1先走完A链表再去走B链表，p2同理，当两者相同时，就指向公共节点。
   while(p1 !== p2){
       p1= p1 === null ? pHead2: p1.next;
       p2 = p2=== null ? pHead1: p2.next;
   }
    return p1;
}

发表于 2021-10-01 15:12:32 回复(0)
Javascript
println()头像 println() 
function FindFirstCommonNode(pHead1, pHead2)
{
    // write code here
    let p1 = pHead1, p2 = pHead2
    while(p1 !== p2){
        if(p1 !== null){
            p1 = p1.next
        } else{
            p1 = pHead2
        }
        if(p2 !== null){
            p2 = p2.next
        }else{
            p2 = pHead1
        }
    }
    return p1
    
}

发表于 2021-09-24 22:13:08 回复(0)
Javascript
你有尾巴吗头像 你有尾巴吗 
function FindFirstCommonNode(pHead11, pHead22)
{
    // write code here
    let pHead1=pHead11;
    let pHead2=pHead22;
    while(pHead1!=pHead2){
        pHead1=pHead1==null?pHead22:pHead1.next;
        pHead2=pHead2==null?pHead11:pHead2.next;
    }
    return  pHead2;
}
module.exports = {
    FindFirstCommonNode : FindFirstCommonNode
};

编辑于 2021-07-19 11:08:31 回复(0)
JavaScript
「Clear•」头像 「Clear•」
使用对象保存pHead1所有值以及所在链表的位置，遍历pHead2，查找共同有的结点，再选出所在链表位置最早的那个结点即为第一个公共结点。 
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function FindFirstCommonNode(pHead1, pHead2)
{
    let list = {};
    let path = 1;
    while(pHead1){
        list[pHead1.val] = path;
        pHead1 = pHead1.next;
        path ++;
    }
    let min = path;
    let result = null;
    while(pHead2){
        if(list[pHead2.val] && list[pHead2.val] <= min){
            result = pHead2;
            min = list[pHead2.val];
        }
        pHead2 = pHead2.next;
    }
    
    return result;
}


发表于 2021-06-16 13:33:21 回复(1)
JavaScript
IPzzzi头像 IPzzzi 
function FindFirstCommonNode(pHead1, pHead2)
{
    // write code here
    if(!pHead1 || !pHead2){
        return null;
    }
    var pA = pHead1,
        pB = pHead2;
    while(pA != pB){
        pA = pA === null ? pHead2 : pA.next;
        pB = pB === null ? pHead1 : pB.next;
    }
    return pA;
}

发表于 2021-03-22 16:08:10 回复(0)
JavaScript
别卷啦！头像 别卷啦！
双指针  
function FindFirstCommonNode(pHead1, pHead2)
{
    // write code here
    let h1 = pHead1, h2 = pHead2
    while(h1!==h2){                //如果没有相交
        h1 = h1 ? h1.next : pHead2 //h1结束接入h2
        h2 = h2 ? h2.next : pHead1 //h2结束接入h1
    }
    return h1
}

发表于 2020-12-28 12:17:30 回复(0)
JavaScript
Helianthuswhite头像 Helianthuswhite 
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/

/**
 * 我的解题思路：
 * 1.emmmm，这个问题之前面头条的时候被问到过，没答出来的但是面试官给讲了思路哈哈哈，这次做出来了
 * 2.先让两个链表同时开始遍历，直到较短的那个链表所有节点都被遍历
 * 3.让较长的链表从头开始遍历，直到第二步中剩余部分遍历完成，此时长链表剩余部分与短链表长度相同
 * 4.直接顺序遍历两个链表，找到节点值相同的节点并返回即可，若找不到相同节点，返回null
 * 
 * @param {*} pHead1 
 * @param {*} pHead2 
 */
function FindFirstCommonNode(pHead1, pHead2)
{
    // write code here
    let temp1 = pHead1;
    let temp2 = pHead2;
    while (temp1 && temp2) {
        temp1 = temp1.next;
        temp2 = temp2.next;
    }
    while (temp1) {
        pHead1 = pHead1.next;
        temp1 = temp1.next;
    }
    while (temp2) {
        pHead2 = pHead2.next;
        temp2 = temp2.next;
    }
    while (pHead1 && pHead2 && pHead1.val !== pHead2.val) {
        pHead1 = pHead1.next;
        pHead2 = pHead2.next;
    }
    return pHead1;
}

/**
 * 评论区TOP的解题思路：
 * 1.思路还是那个思路，跟我的类似，只不过它采取了更简洁的写法
 * 2.遍历两个链表，直到找到相同的节点，结束遍历（在JS中无法直接比较节点，这里采用JSON.stringify转成字符串再比较的方式处理）
 * 3.若未找到相同节点，则继续遍历，如果发现短链表遍历结束，那么将短链表指向长链表的头部继续进行遍历，此时遍历的部分为全新的长链表和剩余部分的长链表
 * 4.在之前长链表剩余部分遍历完成之后，另一个长链表已经走出了多出的长度，此时让为空的长链表指向短链表的头部，这样得到的两个链表长度就一致了
 * 5.继续进行遍历，直到找到相同节点即可
 * 
 * @param {*} pHead1 
 * @param {*} pHead2 
 */
function topFindFirstCommonNode(pHead1, pHead2)
{
    // write code here
    let temp1 = pHead1;
    let temp2 = pHead2;
    while (JSON.stringify(temp1) !== JSON.stringify(temp2)) {
        temp1 = temp1 ? temp1.next : pHead2;
        temp2 = temp2 ? temp2.next : pHead1;
    }
    return temp1;
}

发表于 2020-06-13 22:26:48 回复(0)
JavaScript
火星人再也不用种土豆了头像 火星人再也不用种土豆了
js版链表转数组查询，时间复杂度O（m+n），易懂 
function ListNode(x){
    this.val = x;
    this.next = null;
}
function FindFirstCommonNode(pHead1, pHead2)
{
    // write code here
    var arr1 = [];
    var curr1 = pHead1; 
    var curr2 = pHead2;
    while(curr1 != null){
        arr1.push(curr1.val);
        curr1 = curr1.next;
    }
    while(curr2 != null){
        if(arr1.includes(curr2.val))
            return curr2;
        curr2 = curr2.next;
    }
}
module.exports = {
    FindFirstCommonNode : FindFirstCommonNode
};


发表于 2020-03-09 21:26:14 回复(0)
JavaScript
希望一切到好头像 希望一切到好
哈哈，复杂度太高，过不去，快慢针。（vscode可以跑出结果） 
function ListNode(x){
  this.val = x;
  this.next = null;
}

function FindFirstCommonNode(pHead1, pHead2)
{
    // 让链表成环
    let pNode2 = pHead2;
    while (pNode2.next) {
        pNode2 = pNode2.next;
    }
    pNode2.next = pHead2;
    
    // 快慢针判断成环链表的环起点
    let fast = pHead1;
    let slow = pHead1;
    while (fast && fast.next) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            fast = pHead1;
            while (fast != slow) {
                fast = fast.next;
                slow = slow.next;
            }
            
            return fast;
        }
    }
    
    return null;
}



发表于 2019-11-24 18:01:32 回复(0)
JavaScript
Bytedancer2021头像 Bytedancer2021 
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function FindFirstCommonNode(pHead1, pHead2)
{
    // write code here
    let len1 = 0;
    let len2 = 0;
    let curr1 = pHead1;
    let curr2 = pHead2;
    while(curr1){
        len1 ++;
        curr1 = curr1.next;
    }
    while(curr2){
        len2 ++;
        curr2 = curr2.next;
    }
    curr1 = pHead1;
    curr2 = pHead2;
    if(len1 > len2){
        let diff = len1 - len2;
        while(diff--){
            curr1 = curr1.next;
        }
    }else{
        let diff = len2 - len1;
        while(diff--){
            curr2 = curr2.next;
        }
    }
    while(curr1 !== curr2){
        curr1 = curr1.next;
        curr2 = curr2.next;
    }
    return curr1;
}

发表于 2019-10-05 13:50:32 回复(0)
JavaScript
莫得名字的头像 莫得名字的
  • 遍历第一个链表，存Map
  • 遍历第二个链表，查是否存在相同节点 
function ListNode(x) {
  this.val = x;
  this.next = null;
}

function FindFirstCommonNode(pHead1, pHead2) {
  // write code here
  let myMap = new Map();
  let p = pHead1;
  let q = pHead2;

  while (p) {
    myMap.set(p, 1);
    p = p.next;
  }

  while (q) {
    if (myMap.has(q)) {
      return q;
    }
    q = q.next;
  }
  return;
}



var l1 = new ListNode(1);
var l2 = new ListNode(2);
var l3 = new ListNode(3);
var l4 = new ListNode(4);
var l5 = new ListNode(5);

l1.next = l2;
l2.next = l3;
l3.next = l4;
l4.next = l5;

var l6 = new ListNode(6);
var l7 = new ListNode(7);
var l8 = new ListNode(8);
var l9 = new ListNode(9);

l6.next = l7;
l7.next = l8;
l8.next = l3;

let res = FindFirstCommonNode(l1, l6);
console.log(res);
发表于 2019-09-03 15:07:55 回复(0)
JavaScript
assmdx头像 assmdx
利用js对象可以动态增加属性的特性先打标记，再检测即可 
function ListNode(x){
    return {
        val:x,
        next:null
    }
}
function FindFirstCommonNode(pHead1, pHead2)
{
    // write code here
    while(pHead1) {
        pHead1.tag = true
        pHead1 = pHead1.next
    }
    while(pHead2) {
        if(pHead2.tag) {
            pHead2.tag = undefined
            return pHead2
        } else {
            pHead2 = pHead2.next
        }
    }
    return null
}



发表于 2019-08-24 00:05:49 回复(0)
JavaScript
江沢直树头像 江沢直树

两个指针，分别走一遍head1和head2链表，由于先走1后走2和先走2后走1的步数一样，所以两个指针就会在链表的交点相遇。

function FindFirstCommonNode(head1, head2) {
    let p1 = head1, p2 = head2;
    while (p1 != p2) {
        if (p1 == null) p1 = head2;
        else p1 = p1.next;
        if (p2 == null) p2 = head1;
        else p2 = p2.next;
    }
    return p1;
}
发表于 2019-06-13 10:24:50 回复(0)
JavaScript
不去大厂不换昵称头像 不去大厂不换昵称
快慢指针方法
1.先找到两个链表的长度
2.让长一点的链表先走几步，直到和短链表剩余长度相同
3.两个链表一起前进，比较获得第一个相等的节点
时间复杂度O(M+N) 空间复杂度O(0) 
    function FindFirstCommonNode(pHead1, pHead2) {
      if (!pHead1 || !pHead2) { return null; }
      // 获取链表长度
      let length1 = getLength(pHead1);
      let length2 = getLength(pHead2);
      // 长链表先行
      let lang, short, interval;
      if (length1 > length2) {
        lang = pHead1;
        short = pHead2;
        interval = length1 - length2;
      } else {
        lang = pHead2;
        short = pHead1;
        interval = length2 - length1;
      }
      while (interval--) {
        lang = lang.next;
      }
      // 找相同节点
      while (lang) {
        if (lang === short) {
          return lang;
        }
        lang = lang.next;
        short = short.next;
      }
      return null;
    }

    function getLength(head) {
      let current = head;
      let result = 0;
      while (current) {
        result++;
        current = current.next;
      }
      return result;
    }

发表于 2019-02-25 23:59:56 回复(0)
JavaScript
QQ群头像 QQ群 

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function FindFirstCommonNode(pHead1, pHead2)
{
    // write code here
    var len1 = 0;  //记录pHead1的长度
    var len2 = 0;  //记录pHead2的长度
    var p1=pHead1;  //指向pHead1的首节点
    var p2=pHead2;  //指向pHead2的首节点
    
    //遍历链表pHead1，记录其长度len1
    while(p1 != null){
        len1++;
        p1=p1.next;
    }
    
    //遍历链表pHead2，记录其长度len2
    while(p2 != null){
        len2++;
        p2=p2.next;
    }
    
    //比较len1和len2大小，对于更长的链表，先指向其第|len1-len2|个节点
    p1=pHead1;
    p2=pHead2;
    if(len1 > len2){
        var num = len1-len2;
        for(var i=0;i<num; i++){
            p1=p1.next;
        }
    }
    if(len1 < len2){
        var num = len2-len1;
        for(var i=0;i<num; i++){
            p2=p2.next;
        }
    }
    
    //以当前p1，p2所指向的节点为基础，依次比较其指向的节点是否相同，若不相同，则指向next节点；若相同，则该节点为第一个公共节点，返回当前节点。
    while(p1 != null){
        if(p1 == p2){
            return p1;
        }
        p1=p1.next;
        p2=p2.next;
    }
    return false;
    
}

发表于 2018-05-29 15:34:28 回复(0)
提交观点

问题信息

链表
难度：
22条回答 128059浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号