16.合并两个排序的链表

题目描述：

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

知识点：

• 链表，归并排序

解题思路：

• 这道题是一道典型的可以使用归并排序思路的题，只不过由原来数组长度判断变成了由指针判断，两个指针都指向空为止
• 比较两个指针所指值的大小，然后移动指针

解题代码：

function Merge(pHead1, pHead2)
{
    // write code here
    let p1 = pHead1;
    let p2 = pHead2;
    let l3 = new ListNode(0);
    let p3 = l3;
    while(p1 || p2){
        if(p1 && p2) {
            if(p1.val < p2.val) {
                p3.next = new ListNode(p1.val);
                p3 = p3.next;
                p1 = p1.next;
            }else {
                p3.next = new ListNode(p2.val);
                p3 = p3.next;
                p2 = p2.next;
            }
        }else if(p1) {
            p3.next = new ListNode(p1.val);
            p3 = p3.next;
            p1 = p1.next;
        }else if(p2){
            p3.next = new ListNode(p2.val);
            p3 = p3.next;
            p2 = p2.next;
        }
    }
    return l3.next;
}