Algorithm-Day27-Merge-Two-Sorted-Lists-lc-21

Posted on In , Views:

🧩 Problem Description

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list and return the new head.

Example:

1
2
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

💡 Intuition

This is similar to the merge step in merge sort.

At each step, compare the two current nodes:

  • Choose the smaller one
  • Move its pointer forward

🔢 Java Code (Iterative)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                curr.next = list1;
                list1 = list1.next;
            } else {
                curr.next = list2;
                list2 = list2.next;
            }
            curr = curr.next;
        }

        // Append remaining nodes
        curr.next = (list1 != null) ? list1 : list2;

        return dummy.next;
    }
}

🔁 Java Code (Recursive)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;

        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(n + m)
  • Space Complexity:
    • Iterative: O(1)
    • Recursive: O(n + m) due to call stack

✍️ Summary

  • A classic linked list problem — appears in merge sort, linked list manipulation, and more.
  • Be comfortable with both iterative and recursive approaches.
  • Dummy node makes code simpler and cleaner.

One of the most fundamental problems to master for linked list and recursion.