JavaScript对有序链表的合并详解

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

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;
};

Atas ialah kandungan terperinci JavaScript对有序链表的合并详解. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!