首页  >  文章  >  web前端  >  js中找到两个链表的第一个公共结点的算法

js中找到两个链表的第一个公共结点的算法

不言
不言原创
2018-07-23 11:00:141496浏览

这篇文章给大家分享的内容是关于js中找到两个链表的第一个公共结点的算法  ,有一定的参考价值,有需要的朋友可以参考一下。

题目描述

输入两个链表,找出它们的第一个公共结点。

分析

考虑到两个链表不一样长的情况,算出两个链表的长度差,然后长的链表要先把长度差走完,然后两个链表再一起走。

代码实现

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function FindFirstCommonNode(h1, h2)
{
    var h1Len = 0, h2Len = 0;
    var cur = h1;
    
    while(cur!==null){
        h1Len++;
        cur = cur.next;
    }
    
    cur = h2;
    while(cur!==null){
        h2Len++;
        cur = cur.next;
    }
    
    var distance = 0;
    var t1, t2;
    if(h1Len > h2Len){
        t1 = h1;
        t2 = h2;
        distance = h1Len - h2Len;
    }else{
        t1 = h2;
        t2 = h1;
        distance = h2Len - h1Len;
    }
    
    while(distance !== 0){
        t1 = t1.next;
        distance--;
    }
    
    while(t1 !== t2){
        t1 = t1.next;
        t2 = t2.next;
    }
    
    return t1;
}

相关推荐:

js中实现滑动窗口的最大值的算法    

js中利用两个栈实现队列的算法

以上是js中找到两个链表的第一个公共结点的算法的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn