JavaScript对有序链表的合并详解
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了JavaScript对有序链表的合并详解，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1476字，纯文字阅读大概需要3分钟。
内容图文
对于将两个有序链表合并为一个有序链表的问题，严蔚敏版的《数据结构》中用到了一种经典的算法。1.使用两个指针，分别指向两条链表中当前待比较的节点，创建一条新链表，用于存放两条链表中的节点。
2.每次比较完节点元素的大小，将较小的元素节点引入新链表，指针向后移，这个过程持续到指针中有一个为空。
3.把另一个非空指针指向链表的剩余部分，链接到新链表之后，这个归并过程就完成了。
这个算法效率很高，是O(m+n)的，但是它要创建一条新链表。
假如我有个这样的需求：
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对有序链表的合并详解的详细内容，更多请关注Gxl网其它相关文章！
内容总结
以上是互联网集市为您收集整理的JavaScript对有序链表的合并详解全部内容，希望文章能够帮你解决JavaScript对有序链表的合并详解所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。