Q4: Merge Two Sorted Lists

Merge two sorted linked lists into one single sorted list by creating a dummy node and chaining smaller node values iteratively.

Sorted List Merge

function mergeTwoLists(l1, l2) {
  const dummy = { val: 0, next: null };
  let tail = dummy;
  
  while (l1 !== null && l2 !== null) {
    if (l1.val < l2.val) {
      tail.next = l1;
      l1 = l1.next;
    } else {
      tail.next = l2;
      l2 = l2.next;
    }
    tail = tail.next;
  }
  
  tail.next = l1 !== null ? l1 : l2;
  return dummy.next;
}

💡 Compares front nodes of both lists, attaches the smaller node to tail, and advances that list's pointer. Any remaining nodes are appended at the end.

Key Takeaways

A dummy head node simplifies boundary edge cases when building the merged list.
Runs in O(n + m) time complexity where n and m are lengths of the lists.

Knowledge Check

Why is a dummy node used at the start of the algorithm?

Q4: Merge Two Sorted Lists

STAY UPDATED WITH BYTES!