合并两个排序的链表

题目描述

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

思路

先定义一个头结点dummyNode，然后同时遍历两个链表pHead1 和pHead2，判断两个链表结点值的大小，将小的结点添加到dummyNode的后面。

如果pHead2上的结点全部遍历完以后发现pHead1还有未遍历到的结点，那就把pHead1剩下的结点全部添加到dummyNode的后面。

如果pHead1上的结点全部遍历完以后发现pHead2还有未遍历到的结点，那就把pHead2剩下的结点全部添加到dummyNode的后面。

代码

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function Merge(pHead1, pHead2) {
  let dummyNode = new ListNode(0);
  let node = dummyNode;
  while (pHead1 && pHead2) {
    if (pHead1.val <= pHead2.val) {
      node.next = pHead1;
      pHead1 = pHead1.next;
      node = node.next;
    } else {
      node.next = pHead2;
      pHead2 = pHead2.next;
      node = node.next;
    }
  }
  // pHead2先遍历完，pHead1未完
  if (pHead1) {
    node.next = pHead1;
  }
  // pHead1先遍历完，pHead2未完
  if (pHead2) {
    node.next = pHead2;
  }
  return dummyNode.next;
}