JavaScript对有序链表的合并详解-js教程-PHP中文网

JavaScript对有序链表的合并详解

黄舟

发布： 2017-03-18 14:49:20

原创

2096人浏览过

对于将两个有序链表合并为一个有序链表的问题，严蔚敏版的《数据结构》中用到了一种经典的算法。

1.使用两个指针，分别指向两条链表中当前待比较的节点，创建一条新链表，用于存放两条链表中的节点。

2.每次比较完节点元素的大小，将较小的元素节点引入新链表，指针向后移，这个过程持续到指针中有一个为空。

3.把另一个非空指针指向链表的剩余部分，链接到新链表之后，这个归并过程就完成了。

这个算法效率很高，是O(m+n)的，但是它要创建一条新链表。

立即学习“Java免费学习笔记（深入）”；

假如我有个这样的需求：

1.将第二个链表合并到第一个链表中，要求不能生成新链表。

2.第二个链表节点的引用关系不能改动，或者说，不能影响第二条链表。

佳蓝智能应答系统

类似智能机器人程序，以聊天对话框的界面显示，通过输入问题、或点击交谈记录中的超链接进行查询，从而获取访客需要了解的资料等信息。系统自动保留用户访问信息及操作记录。后台有详细的设置和查询模块。适用领域：无人职守的客服系统自助问答系统智能机器人开发文档、资源管理系统……基本功能：设置对话界面的显示参数设置各类展示广告根据来访次数显示不同的欢迎词整合其他程序。

查看详情

该怎么做呢？

对于这个问题，有3点分析：

1.这是一个将第二条链表元素插入第一条链表的问题。

2.插入的节点不能是第二条链表的原节点，而是新节点，否则会影响到第二条链表。

3.外层循环控制遍历第二条链表，内层循环负责插入新节点，所以是O(m*n)的算法。

具体实现：

//将l2合并到l1
var mergeTwoLists = function(l1, l2) {
	//遍历l2链表，将元素一一插入l1
    while(l2){
		//先前的l1元素
        var prev = null;
		//当前的l1元素
        var cur = l1;
		//遍历l1链表，找到可插入l2元素的位置
        while(cur && l2.val > cur.val){
			//记录先前的l1元素
            prev = cur;
			//记录当前的l1元素
            cur = cur.next;
        }
		//生成新的节点
		//注意：并没有利用l2已有的节点
        var newNode = new ListNode(l2.val);
		//插入新节点
		//新节点的next指向当前的l1元素
        newNode.next = cur;
		//如果是在l1链表中间插入
		//或者说新节点有前驱
        if(prev){
			//先前元素的next指向新节点
            prev.next = newNode;
        }//如果新节点插在链表头部
        else{
            l1 = newNode;
        }
        l2 = l2.next;
    }
	//返回l1
    return l1;
};

登录后复制

以上就是JavaScript对有序链表的合并详解的详细内容，更多请关注php中文网其它相关文章！