合并两个排序的链表

题目

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围：0≤n≤1000，−1000≤节点值≤1000
要求：空间复杂度 O(1)，时间复杂度 O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

迭代

function Merge(pHead1, pHead2)
{
    // write code here
    let cur = {
        val:0,
        next:null
    }
    let node = cur
    while(pHead1 && pHead2){
        if(pHead1.val<=pHead2.val){
            node.next = pHead1
            pHead1 = pHead1.next
        }else {
            node.next = pHead2
            pHead2 = pHead2.next
        }
        node = node.next   
    }
    if(pHead1) node.next = pHead1
    else node.next = pHead2
    return cur.next

 - List item

}
module.exports = {
    Merge : Merge
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

递归

function Merge(pHead1, pHead2)
{
    // write code here
    if(pHead1 === null || pHead2 === null){
        return pHead1!=null ? pHead1:pHead2
    }
    if(pHead1.val<=pHead2.val){
        pHead1.next = Merge(pHead1.next,pHead2)
        return pHead1
    }else{
        pHead2.next = Merge(pHead1,pHead2.next)
        return pHead2
    }
}
module.exports = {
    Merge : Merge
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17