Merge Two Sorted Lists

Merging two already sorted linked lists into a single sorted list is a common operation that offers significant performance advantages over sorting a combined list from scratch. This process achieves linear time complexity, `O(n)`, making it highly efficient for large datasets.

How Merging Works

Instead of combining both lists and then applying a sort algorithm (which would typically be `O(n log n)`), merging takes advantage of the pre-sorted nature of the input lists. The core idea is to iterate through both lists simultaneously, comparing their current head nodes and building a new sorted list by picking the smaller element at each step.

Using a Dummy Node Anchor

To simplify the process of building the new merged list, a common technique is to use a "dummy" node. This node acts as an anchor for the head of the new list. A `current` pointer then traverses this new list, appending nodes as they are selected from the input lists. The actual sorted list will begin at `dummy.next`.

Comparing Pointers and Building the List

Start with pointers, say `ptrA` and `ptrB`, at the heads of the two input lists, and a `current` pointer at the dummy node. In a loop, compare the values pointed to by `ptrA` and `ptrB`. The node with the smaller value is appended to `current.next`, and the corresponding pointer (`ptrA` or `ptrB`) is advanced to its next node. The `current` pointer is also advanced to the newly appended node.

function mergeTwoLists(list1, list2):
  dummy = new ListNode(0) // Create a dummy node
  current = dummy

  ptrA = list1
  ptrB = list2

  while ptrA is not null AND ptrB is not null:
    if ptrA.val <= ptrB.val:
      current.next = ptrA
      ptrA = ptrA.next
    else:
      current.next = ptrB
      ptrB = ptrB.next
    current = current.next

  // Attach any remaining nodes from either list
  if ptrA is not null:
    current.next = ptrA
  else:
    current.next = ptrB

  return dummy.next // The head of the merged list

Attaching Remaining Nodes

Once one of the input lists is exhausted (i.e., its pointer becomes `null`), all remaining nodes in the other list are already sorted. These can simply be appended to the end of the new merged list. This final step completes the merge operation in a single pass.

Key takeaways

• Merging two sorted lists is more efficient than sorting from scratch.
• It achieves linear time complexity, `O(n)`, where `n` is the total number of nodes.
• A dummy node simplifies the construction of the new merged list.
• Nodes are added by comparing current heads and advancing pointers.
• Any remaining nodes from an unexhausted list are appended directly.