摘要：關(guān)于鏈表區(qū)別于數(shù)組，數(shù)組的所有的元素在內(nèi)存中都是連續(xù)存儲(chǔ)的，而鏈表則是分散在內(nèi)存中的，通過(guò)指針連接起來(lái)的一種數(shù)據(jù)結(jié)構(gòu)。接下來(lái)，我們嘗試使用合并兩個(gè)有序鏈表。

區(qū)別于數(shù)組，數(shù)組的所有的元素在內(nèi)存中都是連續(xù)存儲(chǔ)的，而鏈表則是分散在內(nèi)存中的，通過(guò)指針連接起來(lái)的一種數(shù)據(jù)結(jié)構(gòu)。接下來(lái)，我們嘗試使用js合并兩個(gè)有序鏈表。

首先我們需要聲明一些我們需要用到的函數(shù)。

每一個(gè)節(jié)點(diǎn)通常最少有兩個(gè)屬性，一個(gè)表示該節(jié)點(diǎn)的值，可以用key來(lái)表示，另外一個(gè)就是指向下一個(gè)節(jié)點(diǎn)的指針，可以用next表示。
先聲明一個(gè)Node類：

function Node (key) {
    this.key = key;
    this.next = null;
}

接著，聲明一個(gè)鏈表類LinkedList：

function LinkedList () {
    //表示鏈表的長(zhǎng)度
    this.length = 0;
    //表示鏈表的頭結(jié)點(diǎn)（第一個(gè)節(jié)點(diǎn)）
    this.head = null;
}

然后，再聲明一個(gè)基本的鏈表方法append，用來(lái)向鏈表尾部插入一個(gè)新節(jié)點(diǎn)：

LinkedList.prototype.append = function (key){
    var node = new Node(key);
    //如果鏈表還沒(méi)有節(jié)點(diǎn)
    if (!this.head) {
        this.head = node;
    } else {
        //通過(guò)循環(huán)找到最后一個(gè)節(jié)點(diǎn)，然后讓最后一個(gè)節(jié)點(diǎn)指向新節(jié)點(diǎn)
        var current = this.head;
        while(current.next){
            current = current.next;
        }
        current.next = node;
    }
    // 修改鏈表的長(zhǎng)度
    this.length++;
}

我們的目的是合并有序鏈表，所以這里，我們先用兩個(gè)有序數(shù)組，去構(gòu)建兩個(gè)有序鏈表：

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);
});

就是把兩個(gè)鏈表中所有key都拿出來(lái)放進(jìn)一個(gè)數(shù)組里，庵后，再對(duì)數(shù)組排序，根據(jù)數(shù)組，重新構(gòu)建一個(gè)鏈表。

function mergeLinkedList (list1, list2) {
    // 存放兩個(gè)鏈表key的數(shù)組
    var array = [];
    // 最終需要返回的新鏈表
    var list = new LinkedList();
    // 第一個(gè)鏈表的頭節(jié)點(diǎn)
    var listHead1 = list1.head;
    // 第二個(gè)鏈表的頭節(jié)點(diǎn)
    var listHead2 = list2.head;

    // 把第一個(gè)鏈表的所有key存進(jìn)數(shù)組
    while (listHead1) {
        array.push(listHead1.key);
        listHead1 = listHead1.next;
    }
    // 把第二個(gè)鏈表的所有key存進(jìn)數(shù)組
    while (listHead2) {
        array.push(listHead2.key);
        listHead2 = listHead2.next;
    }
    // 對(duì)數(shù)組排序
    array = array.sort(function(a, b){
        return a - b;
    })
    // 使用數(shù)組重新構(gòu)建一個(gè)鏈表
    array.forEach(function(key){
        list.append(key);
    });

    return list;
}

function mergeLinkedList (list1, list2) {
    var list = new LinkedList();
    // 第一個(gè)鏈表的頭節(jié)點(diǎn)
    var current1 = list1.head;
    // 第二個(gè)鏈表的頭節(jié)點(diǎn)
    var current2 = list2.head;

    // 用循環(huán)把兩個(gè)鏈表的key按順序插入到新鏈表
    while (current1 && current2) {
        if (current1.key < current2.key) {
            list.append(current1.key);
            current1 = current1.next;
        } else {
            list.append(current2.key);
            current2 = current2.next;
        }
    }

    // 找到新鏈表的最后一個(gè)節(jié)點(diǎn)
    var current = list.head;
    while(current.next){
        current = current.next;
    }

    // 循環(huán)完成以后，把第二個(gè)鏈表剩余部分插入到新鏈表
    if (current2) {
        while (current2) {
            list.append(current2.key);
            current2 = current2.next;
        }
    }
    // 循環(huán)完成以后，把第一個(gè)鏈表剩余部分插入到新鏈表
    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;

    // 如果第二個(gè)鏈表的首節(jié)點(diǎn)key小于第一個(gè)鏈表的首節(jié)點(diǎn)key
    // 則構(gòu)造一個(gè)新節(jié)點(diǎn)，并把新節(jié)點(diǎn)插入到第一個(gè)鏈表頭部
    if (listHead1.key > listHead2.key) {
        var node = new Node(listHead2.key);
        node.next = listHead1;
        list1.head = listHead1 = previous = node;
        listHead2 = listHead2.next;
    }
    // 循環(huán)比較兩個(gè)鏈表的key，把第二個(gè)鏈表中的key插入到第一個(gè)鏈表合適的位置
    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; 
        }
    }
    // 如果第二個(gè)鏈表比較長(zhǎng)，則把剩余部分插入到第一個(gè)鏈表
    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;
    }

    // 修正第一個(gè)鏈表的長(zhǎng)度
    list1.length = list1.length + list2.length;
    return list1;
}

還是構(gòu)造兩個(gè)有序鏈表

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);

自控制臺(tái)查看結(jié)果：

換一組測(cè)試數(shù)據(jù)（arr1和arr2調(diào)換一下）：

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);

看結(jié)果：

來(lái)一個(gè)復(fù)雜點(diǎn)的測(cè)試數(shù)據(jù)：

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);

結(jié)果如下：

以上代碼中，都省去了參數(shù)合法性校驗(yàn)的過(guò)程，真實(shí)環(huán)境里是需要的。