前言

本系列主要整理面试中需要掌握的手撕代码题。本节介绍有序链表的合并。

---

一、BM4 合并两个排序的链表

（1）首先新建一个空链表，并定义一个新指针指向空链表；
（2）如果两个链表都不为空，则比较当前两个链表的值，选择小的加入空链表，并移动指针；
（3）当出现空链表后，就把非空链表都接在新链表后面，最后返回头部指针。
代码如下：

function Merge(pHead1, pHead2)
{
    // write code here
    var newHead = new ListNode();
    var p = newHead;
    while(pHead1 && pHead2){
        if(pHead1.val > pHead2.val){
            p.next = pHead2;
            pHead2 = pHead2.next;
        }else{
            p.next = pHead1;
            pHead1 = pHead1.next;
        }
        p = p.next;
    }
    p.next = (!pHead1) ? pHead2 : pHead1
    return newHead.next
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

二、BM5 合并k个已排序的链表

（1） 依次遍历链表中的val，都存放在一个新列表中；
（2）对新列表进行排序；
（3）遍历新列表，不断创建新节点，将新列表变为新链表，并返回。

function mergeKLists( lists ) {
    // write code here
    var newlist = [];
    lists.forEach(item=>{
        while(item){
            newlist.push(item.val)
            item = item.next
        }
    })
    newlist.sort((a,b)=> {return a-b})
    var newNode = new ListNode();
    var p = newNode;
    newlist.forEach(item=>{
        var q = new ListNode(item);
        p.next = q;
        p = p.next
    })
    return newNode.next
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19