Merge Linked Lists

Tags

Merge Linked Lists

Category

Linked Lists

Difficulty

Medium

Problem Statement

Given two sorted singly linked lists, merge them into a single sorted linked list. The merged list should be made by splicing together the nodes of the two input lists. Return the head of the merged linked list.

Intuition

Since both lists are already sorted, we can merge them in a single pass using a technique similar to the merge step in merge sort. At each step, compare the current nodes of both lists and append the smaller one to the result. This produces a sorted merged list without needing to sort afterward.

Approach

  1. Create a dummy head node to simplify edge cases.
  2. Maintain a current pointer starting at the dummy head.
  3. While both lists have remaining nodes: a. Compare the values at the heads of the two lists. b. Attach the smaller node to current.next. c. Advance the pointer of the list from which the node was taken. d. Advance current.
  4. When one list is exhausted, attach the remaining portion of the other list to current.next.
  5. Return dummy.next.

Pseudocode

function mergeSortedLists(list1, list2):
    dummy = new Node(0)
    current = dummy

    while list1 is not null and list2 is not null:
        if list1.value <= list2.value:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next

    if list1 is not null:
        current.next = list1
    else:
        current.next = list2

    return dummy.next

Time & Space Complexity

  • Time: O(n + m), where n and m are the lengths of the two lists. Each node is processed exactly once.
  • Space: O(1). The merge is done in place by rearranging pointers; no new nodes are created.

Key Insights

  • The dummy head node eliminates special-case handling for the first node of the merged list.
  • This is the same merge operation used in merge sort, which is why merge sort on linked lists is efficient and natural.
  • The merge is stable: equal elements retain their original relative order.
  • When one list is exhausted, the remaining portion of the other list is already sorted and can be appended directly.

Edge Cases

  • One or both lists are empty: return the non-empty list (or null if both are empty).
  • One list is entirely smaller than the other: all nodes from the smaller list come first.
  • Lists of vastly different lengths.
  • Lists with duplicate values across both lists.
  • Single-node lists.

Linked mentions