JS實(shí)現(xiàn)的合并兩個(gè)有序鏈表算法示例

<script>
function Node(element) {
  this.element = element;//當(dāng)前節(jié)點(diǎn)的元素
  this.next = null;//下一個(gè)節(jié)點(diǎn)鏈接
}
function List() {
  this.head = new Node("head");//頭節(jié)點(diǎn)
  this.find = find;//查找節(jié)點(diǎn)
  this.insert = insert;//插入節(jié)點(diǎn)
  this.remove = remove;//刪除節(jié)點(diǎn)
  this.display = display;//顯示鏈表
  this.findPrevious = findPrevious; //查找前一個(gè)節(jié)點(diǎn)
}
//下面的函數(shù)是操作方法：對(duì)應(yīng)List類構(gòu)造函數(shù)中的名稱
//查找給定節(jié)點(diǎn)
function find(item) {
  var currNode = this.head;
  while(currNode.element != item) {
    currNode = currNode.next;
  }
  return currNode;
}
//向鏈表插入一個(gè)節(jié)點(diǎn)
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;
}
//刪除節(jié)點(diǎn)
function remove(item) {
  var prevNode = this.findPrevious(item);
  if(prevNode.next != null)
    prevNode.next = prevNode.next.next;
}
//從鏈表中刪除節(jié)點(diǎn)時(shí)，我們先要找個(gè)待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，找到后，我們修改它的 next 屬性，使其不在指向待刪除的節(jié)點(diǎn)，而是待刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。那么，我們就得需要定義一個(gè) findPrevious 方法遍歷鏈表，檢查每一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)是否存儲(chǔ)待刪除的數(shù)據(jù)。如果找到，返回該節(jié)點(diǎn)，這樣就可以修改它的 next 屬性了。
//查找?guī)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
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) {
  // 模仿鏈表的數(shù)據(jù)結(jié)構(gòu)
  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>