合并两个有序链表

21. 合并两个有序链表

来源：力扣（LeetCode） 链接 (opens new window)：https://leetcode.cn/problems/merge-two-sorted-lists/

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

github (opens new window)

问题

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

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

思路

方法一

双指针，遍历

var mergeTwoLists = function (list1, list2) {
  let head = new ListNode(0);
  let pHead = head;

  let p1 = list1;
  let p2 = list2;

  while (p1 !== null && p2 !== null) {
    if (p1.val < p2.val) {
      head.next = p1;
      p1 = p1.next;
    } else {
      head.next = p2;
      p2 = p2.next;
    }

    head = head.next;
  }

  if (p1) {
    head.next = p1;
  }

  if (p2) {
    head.next = p2;
  }

  return pHead.next;
};

方法二

递归的遍历

/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
  if (list1 === null) {
    return list2;
  }
  if (list2 === null) {
    return list1;
  }

  if (list1.val < list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  } else {
    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
  }
};