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

以上是JavaScript對有序鍊錶的合併詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！