Mohith

Posted on Mar 20

Merge Two Sorted Lists -CA15

#algorithms #beginners #coding #computerscience

My Thinking and Approach

Introduction

In this problem, I was given two sorted linked lists and asked to merge them into a single sorted linked list.

At first, I thought it would be similar to merging arrays, but since this involves linked lists, I had to carefully manage pointers.

Problem Statement

Given two sorted linked lists list1 and list2
Merge them into a single sorted linked list
Return the head of the merged list

My Initial Thought

Initially, I thought:

Convert linked lists into arrays
Merge arrays
Convert back to linked list

But this approach:

Uses extra space
Is not optimal

So I needed to solve it directly using linked list operations.

Optimized Approach

I realized this is similar to the merge step in merge sort.

Idea

Compare nodes from both lists
Pick the smaller one
Move forward
Continue until one list becomes empty

My Approach

Create a dummy node to simplify handling
Use a pointer current to build the result list
Compare values from both lists:
- Attach smaller node to result
- Move that list forward
At the end, attach the remaining list

Code (Java)

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;

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

        if (list1 != null) {
            current.next = list1;
        } else {
            current.next = list2;
        }

        return dummy.next;
    }
}

Example Walkthrough

Example 1

Input:
list1 = [1 → 2 → 4]
list2 = [1 → 3 → 4]

Step-by-step:

Compare 1 and 1 → pick any → [1]
Compare 2 and 1 → pick 1 → [1,1]
Compare 2 and 3 → pick 2 → [1,1,2]
Compare 4 and 3 → pick 3 → [1,1,2,3]
Compare 4 and 4 → pick 4 → [1,1,2,3,4]
Add remaining 4 → [1,1,2,3,4,4]

Output:
[1,1,2,3,4,4]

Example 2

Input:
list1 = [], list2 = []

Output:
[]

Example 3

Input:
list1 = [], list2 = [0]

Output:
[0]

Complexity Analysis

Time Complexity: O(n + m)
Space Complexity: O(1)

Key Takeaways

Linked list problems require careful pointer handling
Dummy node simplifies edge cases
This is similar to merge sort logic

Conclusion

This problem helped me understand how to work with linked lists efficiently. It also improved my confidence in handling pointer-based problems, which are very common in coding interviews.

DEV Community