算法：合并两个有序链表

[pengjielee]

准备工作

// 节点类
class Node {
  constructor(value) {
    this.value = value; // 存储值 
    this.next = null;   // 存储下一个节点的引用
  }
}

//链表类
class LinkedList {
  constructor() {
    this.length = 0;   //链表的长度
    this.head = null;  //链表的头结点
  }

  //链表的插入方法
  append(value) { 
  	var node = new Node(value);  //创建节点
  	if(!this.head){
  		this.head = node;          //设置头结点
  	} else {
  		var current = this.head;
  		while(current.next){       //通过循环找到最后一个节点 
  			current = current.next;
  		}
  		current.next = node; 
  	}
  	this.length++;  //修改链表长度
  }

  display() {
  	if(!this.head){
  		return [];
  	} else {
  		var results = [];
  		var current = this.head;
  		for(let i = 0; i < this.length; i++){
  			results.push(current.value);
  			current = current.next;
  		}
  		return results;
  	}
  }
}

// 构建有序链表
var arr1 = [2,4,6,8,9];
var arr2 = [1,3,5,7];

var linklist1 = new LinkedList();
var linklist2 = new LinkedList();

arr1.forEach((item) => linklist1.append(item));
arr2.forEach((item) => linklist2.append(item));

简单粗暴方案

把两个链表中所有key都拿出来放进一个数组里，再对数组排序，根据数组，重新构建一个链表。

var merge = (list1, list2) => {
	var arr = []; // 存储所有key的数组
	var list = new LinkedList(); // 新链表

	var head1 = list1.head;   // 链表1头结点
	var head2 = list2.head;   // 链表2头结点

	while(head1){     // 把链表1的所有值存入数据
		arr.push(head1.value);
		head1 = head1.next;
	}

	while(head2){    // 把链表2的所有值存入数据
		arr.push(head2.value);
		head2 = head2.next;
	}

	arr = arr.sort((a,b) => { return a - b }); // 对数组排序

	arr.forEach((item) => { list.append(item)} ); // 根据数组重新构建链表

	return list;
}

按顺序把两个链表的key插入到新链表

var merge = (list1, list2) => { 
	var list = new LinkedList();   // 新链表

	var head1 = list1.head;   // 链表1头结点
	var head2 = list2.head;   // 链表2头结点

	while(head1 && head2){    // 循环把两个链表的key按顺序插入到新链表
		if(head1.value < head2.value){
			list.append(head1.value);
			head1 = head1.next;
		} else {
			list.append(head2.value);
			head2 = head2.next;
		}
	}

	// 找到链表最后一个节点
	var current = list.head;
	while(current.next){
		current = current.next;
	}

	// 把链表1的剩余部分插入到新链表
	if(head1 && head2 === null){
		while(head1){
			list.append(head1.value);
			head1 = head1.next;
		}
	}

	// 把链表2的剩余部分插入到新链表
	if(head2 && head1 === null){
		while(head2){
			list.append(head2.value);
			head2 = head2.next;
		}
	}

	return list;
}

合并到第一个链表

var merge = (list1, list2) => {
	var head1 = list1.head;   // 链表1头结点
	var head2 = list2.head;   // 链表2头结点

	var head = head1;

	//如果第二个链表的值小于第一个链表的值，则创建一个新节点，并把新节点插入到第一个链表头部
	if(head2.value < head1.value){
		var node = new Node(head2.value);
		node.next = head1;
		list1.head = head1 = head = node;
		head2 = head2.next;
	}

	// 循环比较两个链表的value，把第二个链表中的value插入到第一个链表合适的位置
	while(head1 && head2){
		if(head2.value < head1.value){
			var node = new Node(head2.value);
			node.next = head.next;
			head.next = node;
			head = node;
			head2 = head2.next;
		} else {
			head = head1;
			head1 = head1.next;
		}
	}

	// 如果第二个链表比较长，则把剩余部分插入到第一个链表
	while(head2){
		var node = new Node(head2.value);
		if(head1){
			head1.next = node;
			head1 = node;
		}else if(head){
			head.next = node;
			head = node;
		}
		head2 = head2.next;
	}

	// 修正第一个链表的长度
	list1.length = list1.length + list2.length;
	return list1;
}

C语言实现

从两链表第一个结点开始比较结点的值，取较小者作为合并链表的元素，依次进行；后面如果有一个链表为空，则直接把不为空的链表接到合并链表的后面。

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
}

ListNode* mergeList(ListNode* 11, ListNode* 12){
	ListNode* temp1 = 11;
	ListNode* temp2 = 12;

	ListNode* ret = new ListNode(0);

	ListNode* ret1 = ret;

	while(temp1 != NULL && temp2 != NULL){
		if(temp1->val > temp2->val){
			ret->next = temp2; //??
			ret = ret->next;   //??
			temp2 = temp2->next;
		} else {
			ret->next = temp1;  //??
			ret = ret->next;    //??
			temp1 = temp1->next;
		}
	}

	if(temp1 == NULL && temp2 != NULL){
		ret->next = temp2;
	}

	if(temp2 == NULL && temp1 != NULL){
		ret->next = temp1;
	}
}

js合并有序链表
https://segmentfault.com/a/1190000011647929

合并两个有序链表
https://mp.weixin.qq.com/s/afY9Xf4pB2ECHczJhDcY4w

es6 class
http://caibaojian.com/es6/class.html

es6 class
https://www.runoob.com/w3cnote/es6-class.html