JavaScript对有序链表的合并详解
全部回答
对于将两个有序链表合并为一个有序链表的问题，严蔚敏版的《数据结构》中用到了一种经典的算法。1。使用两个指针，分别指向两条链表中当前待比较的节点，创建一条新链表，用于存放两条链表中的节点。
2。每次比较完节点元素的大小，将较小的元素节点引入新链表，指针向后移，这个过程持续到指针中有一个为空。 3。把另一个非空指针指向链表的剩余部分，链接到新链表之后，这个归并过程就完成了。
这个算法效率很高，是O(m+n)的，但是它要创建一条新链表。假如我有个这样的需求：1。将第二个链表合并到第一个链表中，要求不能生成新链表。2。第二个链表节点的引用关系不能改动，或者说，不能影响第二条链表。
该怎么做呢？对于这个问题，有3点分析：1。这是一个将第二条链表元素插入第一条链表的问题。2。插入的节点不能是第二条链表的原节点，而是新节点，否则会影响到第二条链表。3。
外层循环控制遍历第二条链表，内层循环负责插入新节点，所以是O(m*n)的算法。具体实现：//将l2合并到l1var 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;};。 。
类似问题换一批
热点推荐
热度TOP
-
妻子不怀孕岳母教我每天给妻子按摩这有用吗？
203人阅读
-
身上痒痒预示10种大病是哪些啊
38人阅读
-
南通文峰妇科坑人？
30人阅读
-
胎心监护异常不一定就是缺氧 给宝妈们提个醒？
12095人阅读
-
成都无痛人流哪家好棕南
47人阅读
-
能瞒得住吗？。。。
39人阅读