Course4all
Join us on telegram
Home/dsa/Linked List Patterns/Merge Two Sorted Lists

Merge Two Sorted Lists

Master this topic with zero to advance depth.

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Visual Representation

L1: 1 -> 2 -> 4 L2: 1 -> 3 -> 4 Result: 1 -> 1 -> 2 -> 3 -> 4 -> 4
Easy

Examples

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
Approach 1

Level I: Iterative

Intuition

Use a dummy node and a tail pointer. Compare the heads of both lists, attach the smaller node to the tail, and move pointers forward.

Visual Pointer Walk

L1: [1] -> [3] L2: [2] -> [4] 1. Compare 1 and 2. Attach 1. Tail=[1], L1=[3] 2. Compare 3 and 2. Attach 2. Tail=[2], L2=[4] 3. Compare 3 and 4. Attach 3. Tail=[3], L1=null 4. Attach remaining L2: Tail points to [4].
⏱ O(N + M) where N, M are lengths of the lists💾 O(1)

Detailed Dry Run

L1: 1->2, L2: 1->3. Dummy -> 1 (L1) -> 1 (L2) -> 2 (L1) -> 3 (L2).

java
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode 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;
}

⚠️ Common Pitfalls & Tips

Don't forget to attach the remaining nodes at the end.

Approach 2

Level III: Optimized In-place (No Dummy)

Intuition

Merge the lists in-place by always picking the smaller node as the current head and moving pointers. This avoids the use of a dummy node by handling the first node comparison separately.

⏱ O(N + M)💾 O(1)

Detailed Dry Run

L1: 1->3, L2: 2->4.

  1. L1.val (1) < L2.val (2). Result head is 1.
  2. Iterate and link nodes in-place.
java
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    ListNode head = null;
    if (l1.val <= l2.val) { head = l1; l1 = l1.next; } 
    else { head = l2; l2 = l2.next; }
    ListNode curr = head;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
        else { curr.next = l2; l2 = l2.next; }
        curr = curr.next;
    }
    curr.next = (l1 != null) ? l1 : l2;
    return head;
}

⚠️ Common Pitfalls & Tips

Must handle the head assignment carefully to avoid null pointer exceptions.

← Previous QuestionReverse Nodes in k-Group
Next Question →Reverse Linked List