首頁 > web前端 > js教程 > JavaScript對有序鍊錶的合併詳解

JavaScript對有序鍊錶的合併詳解

黄舟
發布: 2017-03-18 14:49:20
原創
1896 人瀏覽過

對於將兩個有序鍊錶合併為一個有序鍊錶的問題,嚴蔚敏版的《資料結構》中用到了一種經典的演算法。

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中文網其他相關文章!

來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
最新問題
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板