16-合并两个排序的链表-(常规做法|递归)

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

代码：

• 常规解法：

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/

function Merge(pHead1, pHead2)
{
    // write code here
    var p3 = new ListNode(0);
    var p4 = p3;
    while(pHead1 && pHead2){
        if(pHead1.val >pHead2.val){
            p3.next = pHead2;
            p3 = p3.next;
            pHead2 = pHead2.next;
        }else{
            p3.next = pHead1;
            p3 = p3.next;
            pHead1 = pHead1.next;
        }
    }
    if(pHead1){
            p3.next = pHead1;
    }
    if(pHead2){
            p3.next = pHead2;
    }
    return p4.next;
}

• 递归(速度快一点点）：

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/

function Merge(pHead1, pHead2)
{
    // write code here
    let p3;
    if(pHead1===null){
        return pHead2;
    }
    if(pHead2===null){
        return pHead1;
    }
    if(pHead1.val>pHead2.val){
        p3 = pHead2;
        p3.next = Merge(pHead1,pHead2.next);
    }else{
        p3 = pHead1;
        p3.next = Merge(pHead1.next,pHead2);
    }
    return p3;
}