JS实现的合并两个有序链表算法示例

本文实例讲述了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>

感兴趣的朋友可以使用在线html/css/javascript代码运行工具：http://tools.jb51.net/code/htmljsrun测试上述代码，查看运行效果。

更多关于javascript相关内容感兴趣的读者可查看本站专题：《javascript数学运算用法总结》、《javascript数据结构与算法技巧总结》、《javascript数组操作技巧总结》、《javascript排序算法总结》、《javascript遍历算法与技巧总结》、《javascript查找算法技巧总结》及《javascript错误与调试技巧总结》

希望本文所述对大家javascript程序设计有所帮助。