21.合并两个有序链表

题目

LeetCode 简单

题目

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

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

题解

迭代 O(n+m) O(1)

function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null,
): ListNode | null {
  const res = { val: 0, next: null }
  let p = res
  let p1 = list1
  let p2 = list2
  while (p1 && p2) {
    if (p1.val < p2.val) {
      p.next = p1
      p1 = p1.next
    } else {
      p.next = p2
      p2 = p2.next
    }
    p = p.next
  }
  if (p1) {
    p.next = p1
  }
  if (p2) {
    p.next = p2
  }
  return res.next
}

const l1 = new LinkedList([1, 2, 4])
const l2 = new LinkedList([1, 3, 4])
console.log('🌰', mergeTwoLists(l1.head, l2.head))