对于将两个有序链表合并为一个有序链表的问题,严蔚敏版的《数据结构》中用到了一种经典的算法。
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对有序链表的合并详解的详细内容,更多请关注php中文网其它相关文章!
已抢16453个
抢已抢49406个
抢已抢4289个
抢已抢4196个
抢已抢7191个
抢已抢3240个
抢