摘要:關于鏈表區別于數組,數組的所有的元素在內存中都是連續存儲的,而鏈表則是分散在內存中的,通過指針連接起來的一種數據結構。接下來,我們嘗試使用合并兩個有序鏈表。
關于鏈表
一些準備區別于數組,數組的所有的元素在內存中都是連續存儲的,而鏈表則是分散在內存中的,通過指針連接起來的一種數據結構。接下來,我們嘗試使用js合并兩個有序鏈表。
首先我們需要聲明一些我們需要用到的函數。
鏈表中的節點每一個節點通常最少有兩個屬性,一個表示該節點的值,可以用key來表示,另外一個就是指向下一個節點的指針,可以用next表示。
先聲明一個Node類:
function Node (key) { this.key = key; this.next = null; }鏈表類
接著,聲明一個鏈表類LinkedList:
function LinkedList () { //表示鏈表的長度 this.length = 0; //表示鏈表的頭結點(第一個節點) this.head = null; }鏈表的插入節點方法
然后,再聲明一個基本的鏈表方法append,用來向鏈表尾部插入一個新節點:
LinkedList.prototype.append = function (key){ var node = new Node(key); //如果鏈表還沒有節點 if (!this.head) { this.head = node; } else { //通過循環找到最后一個節點,然后讓最后一個節點指向新節點 var current = this.head; while(current.next){ current = current.next; } current.next = node; } // 修改鏈表的長度 this.length++; }構造兩個有序鏈表
我們的目的是合并有序鏈表,所以這里,我們先用兩個有序數組,去構建兩個有序鏈表:
var arr1 = [2, 4, 6, 8]; var arr2 = [1, 3, 5, 7]; var list1 = new LinkedList(); var list2 = new LinkedList(); arr1.forEach(function(key){ list1.append(key); }); arr2.forEach(function(key){ list2.append(key); });合并有序鏈表 最簡單的方案
就是把兩個鏈表中所有key都拿出來放進一個數組里,庵后,再對數組排序,根據數組,重新構建一個鏈表。
function mergeLinkedList (list1, list2) { // 存放兩個鏈表key的數組 var array = []; // 最終需要返回的新鏈表 var list = new LinkedList(); // 第一個鏈表的頭節點 var listHead1 = list1.head; // 第二個鏈表的頭節點 var listHead2 = list2.head; // 把第一個鏈表的所有key存進數組 while (listHead1) { array.push(listHead1.key); listHead1 = listHead1.next; } // 把第二個鏈表的所有key存進數組 while (listHead2) { array.push(listHead2.key); listHead2 = listHead2.next; } // 對數組排序 array = array.sort(function(a, b){ return a - b; }) // 使用數組重新構建一個鏈表 array.forEach(function(key){ list.append(key); }); return list; }按順序把兩個鏈表的key插入到新鏈表
function mergeLinkedList (list1, list2) { var list = new LinkedList(); // 第一個鏈表的頭節點 var current1 = list1.head; // 第二個鏈表的頭節點 var current2 = list2.head; // 用循環把兩個鏈表的key按順序插入到新鏈表 while (current1 && current2) { if (current1.key < current2.key) { list.append(current1.key); current1 = current1.next; } else { list.append(current2.key); current2 = current2.next; } } // 找到新鏈表的最后一個節點 var current = list.head; while(current.next){ current = current.next; } // 循環完成以后,把第二個鏈表剩余部分插入到新鏈表 if (current2) { while (current2) { list.append(current2.key); current2 = current2.next; } } // 循環完成以后,把第一個鏈表剩余部分插入到新鏈表 if (current1) { while (current1) { list.append(current1.key); current1 = current1.next; } } return list; }合并到第一個鏈表
function mergeLinkedList (list1, list2) { var listHead1 = list1.head; var listHead2 = list2.head; var previous = listHead1; // 如果第二個鏈表的首節點key小于第一個鏈表的首節點key // 則構造一個新節點,并把新節點插入到第一個鏈表頭部 if (listHead1.key > listHead2.key) { var node = new Node(listHead2.key); node.next = listHead1; list1.head = listHead1 = previous = node; listHead2 = listHead2.next; } // 循環比較兩個鏈表的key,把第二個鏈表中的key插入到第一個鏈表合適的位置 while (listHead1 && listHead2) { if (listHead2.key < listHead1.key) { var node = new Node(listHead2.key); node.next = previous.next; previous.next = node; previous = node; listHead2 = listHead2.next; } else { previous = listHead1; listHead1 = listHead1.next; } } // 如果第二個鏈表比較長,則把剩余部分插入到第一個鏈表 while (listHead2) { var node = new Node(listHead2.key); if (listHead1) { listHead1.next = node; listHead1 = node; } else if (previous) { previous.next = node; previous = node; } listHead2 = listHead2.next; } // 修正第一個鏈表的長度 list1.length = list1.length + list2.length; return list1; }結果驗證
還是構造兩個有序鏈表
var arr1 = [2, 4, 6, 8]; var arr2 = [1, 3, 5, 7]; var list1 = new LinkedList(); var list2 = new LinkedList(); arr1.forEach(function(key){ list1.append(key); }); arr2.forEach(function(key){ list2.append(key); }); var list = mergeLinkedList(list1, list2);
自控制臺查看結果:
換一組測試數據(arr1和arr2調換一下):
var arr2 = [2, 4, 6, 8]; var arr1 = [1, 3, 5, 7]; var list1 = new LinkedList(); var list2 = new LinkedList(); arr1.forEach(function(key){ list1.append(key); }); arr2.forEach(function(key){ list2.append(key); }); var list = mergeLinkedList(list1, list2);
看結果:
來一個復雜點的測試數據:
var arr1 = [99, 100, 104, 106]; var arr2 = [1, 3, 5, 7, 102, 103, 107]; var list1 = new LinkedList(); var list2 = new LinkedList(); arr1.forEach(function(key){ list1.append(key); }); arr2.forEach(function(key){ list2.append(key); }); var list = mergeLinkedList(list1, list2);
結果如下:
以上代碼中,都省去了參數合法性校驗的過程,真實環境里是需要的。
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/89206.html
摘要:將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。無非是依次將兩個鏈表每個節點的值對比,取出值較小的節點,添加到新鏈表末尾。將剩余鏈表傳回遞歸函數。 將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。 Merge two sorted linked lists and return it as a n...
摘要:分治算法遞歸每層操作分解將原問題分解成一系列的子問題。分治算法滿足的條件可分解原問題與分解成的小問題具有相同的模式無關聯原問題分解成的子問題可以獨立求解,子問題之間沒有相關性,這一點是分治算法跟動態規劃的明顯區別。 Time:2019/4/10Title: Merge K Sorted ListsDifficulty: DifficultyAuthor: 小鹿 題目:Merge K...
摘要:將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。示例輸入輸出答案參考 將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。 示例: 輸入:1->2->4, 1->3->4輸出:1->1->2->3->4->4 答案參考: /** * Definition for singly-linked list...
摘要:什么意思呢比如上方合并鏈表的代碼,分別明確函數的參數和返回值是什么參數是兩個合并的鏈表結點頭結點。返回值是合并后的鏈表。 Time:2019/4/9Title: Merge Two Sorted ListsDifficulty: EasyAuthor: 小鹿 題目:Merge Two Sorted Lists Merge two sorted linked lists and re...
摘要:示例輸入輸出示例輸入輸出示例輸入輸出提示兩個鏈表的節點數目范圍是和均按非遞減順序排列遞歸法分析遞歸法,和之前的一樣,還是需要先設置跳出判斷,這里設置為空的時候跳出。 ...
閱讀 1216·2023-04-26 00:47
閱讀 3569·2021-11-16 11:53
閱讀 796·2021-10-08 10:05
閱讀 2740·2021-09-22 15:19
閱讀 2982·2019-08-30 15:55
閱讀 2756·2019-08-29 16:55
閱讀 2922·2019-08-29 15:20
閱讀 1112·2019-08-23 16:13