本文實例講述了JS實現的合并兩個有序鏈表算法。分享給大家供大家參考,具體如下:
將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。
示例:
輸入:1->2->4, 1->3->4
輸出:1->1->2->3->4->4
可以直接運行的方案:
<script>function Node(element) { this.element = element;//當前節點的元素 this.next = null;//下一個節點鏈接}function List() { this.head = new Node("head");//頭節點 this.find = find;//查找節點 this.insert = insert;//插入節點 this.remove = remove;//刪除節點 this.display = display;//顯示鏈表 this.findPrevious = findPrevious; //查找前一個節點}//下面的函數是操作方法:對應List類構造函數中的名稱//查找給定節點function find(item) { var currNode = this.head; while(currNode.element != item) { currNode = currNode.next; } return currNode;}//向鏈表插入一個節點function insert(newElement,item) { var newNode = new Node(newElement); var current = this.find(item); if(current == null) return console.log("can't find the item"); newNode.next = current.next; current.next = newNode;}//刪除節點function remove(item) { var prevNode = this.findPrevious(item); if(prevNode.next != null) prevNode.next = prevNode.next.next;}//從鏈表中刪除節點時,我們先要找個待刪除節點的前一個節點,找到后,我們修改它的 next 屬性,使其不在指向待刪除的節點,而是待刪除節點的下一個節點。那么,我們就得需要定義一個 findPrevious 方法遍歷鏈表,檢查每一個節點的下一個節點是否存儲待刪除的數據。如果找到,返回該節點,這樣就可以修改它的 next 屬性了。//查找帶刪除節點的前一個節點function findPrevious(item) { var currNode = this.head; while(currNode.next != null && currNode.next.element != item) { currNode = currNode.next; } return currNode;}//顯示鏈表元素function display() { var current = this.head; while(current.next != null) { console.log(current.next.element); current = current.next; }}/** * @param {Node} l1 * @param {Node} l2 * @return {Node} */var mergeTwoLists = function(l1, l2) { // 模仿鏈表的數據結構 var mergedHead = { element : -1, next : null }, cur = mergedHead; while (l1 && l2){ if(l1.element <= l2.element){ cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = l1 || l2 return mergedHead.next;};let list1 = new List();list1.insert(1,'head');list1.insert(2,1);list1.insert(4,2);console.log(list1.display());let list2 = new List();list2.insert(1,'head');list2.insert(3,1);list2.insert(4,3);console.log(list2.display());console.log(mergeTwoLists(list1.head,list2.head))</script>
查看運行效果。
希望本文所述對大家JavaScript程序設計有所幫助。
新聞熱點
疑難解答