Trộn hai linked list đã sắp xếp (Merge Two Sorted Lists) — cách dùng dummy node để gọn code?

Ý tưởng: Duyệt song song hai list, mỗi bước chọn node nhỏ hơn nối vào đuôi kết quả. Dùng một dummy node đứng đầu để khỏi xử lý riêng trường hợp head — code sạch hơn hẳn.

Hình dung: như trộn hai cọc bài đã xếp tăng dần — lật lá nhỏ hơn ở hai cọc bỏ xuống chồng mới.

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  const dummy = new ListNode(0)
  let tail = dummy
  while (l1 && l2) {
    if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next }
    else { tail.next = l2; l2 = l2.next }
    tail = tail.next
  }
  tail.next = l1 ?? l2 // nối phần còn dư
  return dummy.next
}

Độ phức tạp: thời gian O(n+m), bộ nhớ O(1) (chỉ nối lại node có sẵn, không tạo node mới).

Lưu ý: Dòng tail.next = l1 ?? l2 xử lý phần đuôi còn lại của list dài hơn — quên dòng này là lỗi kinh điển.