[21] 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4

输出：1->1->2->3->4->4

这道题实际上就是一次归并排序的思想，两个有序子数组合并为一个有序数组，只不过形式换成了链表。

非常简单，注意新链表创建头结点即可。

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

var mergeTwoLists = function(l1, l2) {
  const dummy = new ListNode();
  let cur = dummy;
  while (l1 && l2) {
    const node = new ListNode();
    if (l1.val < l2.val) {
      node.val = l1.val;
      l1 = l1.next;
    } else {
      node.val = l2.val;
      l2 = l2.next;
    }
    cur.next = node;
    cur = cur.next;
  }
  if (l1) {
    cur.next = l1;
  }
  if (l2) {
    cur.next = l2;
  }
  return dummy.next;
};