Coding Interview Questions | Merge Two Sorted Lists

December 18th, 2023

Introduction:

This summary will talk about my solution to the binary search problem as seen on leetcode here.

Solution:

function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null
): ListNode | null {
  // Create a dummy node as the starting point for the merged list
  const dummy: ListNode = new ListNode(0);
  let current: ListNode = dummy;

  // Use pointers to iterate through both lists
  let list1Ptr: ListNode | null = list1;
  let list2Ptr: ListNode | null = list2;

  // Compare and merge until one of the lists is exhausted
  while (list1Ptr !== null && list2Ptr !== null) {
    if (list1Ptr.val < list2Ptr.val) {
      current.next = list1Ptr;
      list1Ptr = list1Ptr.next;
    } else {
      current.next = list2Ptr;
      list2Ptr = list2Ptr.next;
    }
    current = current.next;
  }

  // Handle remaining nodes in list1 or list2
  if (list1Ptr !== null) {
    current.next = list1Ptr;
  } else {
    current.next = list2Ptr;
  }

  // The merged list starts from the next of the dummy node
  return dummy.next;
}

Summary:

1. Initialize Pointers:

   • Create a dummy node (dummy) to simplify handling the edge case of an empty merged list.
   • Initialize a current pointer (current) to keep track of the last node in the merged list.

2. Iterative Comparison:

   • Use two pointers, list1Ptr and list2Ptr, to iterate through list1 and list2 respectively.
   • Compare the values of the current nodes pointed to by list1Ptr and list2Ptr.

3. Merge Smaller Node:

   • If the value in list1Ptr is smaller, append it to the merged list and move the list1Ptr to the next node.
   • If the value in list2Ptr is smaller or equal, append it to the merged list and move the list2Ptr to the next node.

4. Continue Until One List is Exhausted:

   • Repeat the comparison and merging process until one of the linked lists (list1 or list2) is exhausted.

5. Handle Remaining Nodes:

   • If there are remaining nodes in list1, append them to the merged list.
   • If there are remaining nodes in list2, append them to the merged list.

6. Final Output:

   • The merged list starts from the next node of the dummy node (dummy.next).

• The time complexity is O(m + n), where m and n are the lengths of list1 and list2 respectively. The algorithm iterates through each node once.
• The space complexity is O(1) as the algorithm uses a constant amount of extra space, excluding the input and output.