21. Merge Two Sorted Lists

Explanation

To merge two sorted linked lists, we can iterate through both lists simultaneously, comparing the values at each node, and linking the nodes in ascending order. We maintain a dummy node as the head of the merged list, and we move a pointer through the merged list while updating the next pointers to connect the nodes in sorted order. Finally, we return the next of the dummy node, which is the head of the merged sorted list.

Time complexity: O(m + n) where m and n are the lengths of the two input lists
Space complexity: O(1)

View Leetcode Problem

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;

    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;
    }

    if (l1 != null) {
        curr.next = l1;
    } else {
        curr.next = l2;
    }

    return dummy.next;
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.