Merging Two Sorted Lists: A Comprehensive Guide

In the realm of data structures, merging two sorted linked lists is a fundamental problem that showcases the efficiency of algorithms. This guide aims to provide a clear and concise explanation of how to merge two sorted linked lists into a single sorted list, complete with a practical coding example.

Problem Statement

Merge two sorted linked lists and return a new sorted list. Splice the nodes from the original lists together to form the new list. For instance, given two lists:

List 1: 1 → 2 → 4
List 2: 1 → 3 → 4

The resultant merged list should be:

1 → 1 → 2 → 3 → 4 → 4

Constraints

Each list will contain 0 to 50 nodes.
Node values will range from -100 to 100.
Both lists are guaranteed to be sorted in non-decreasing order.

Approach to the Solution

To solve this problem, a systematic approach is employed:

Initialization: Create a dummy node that will serve as the head of the merged list. This simplifies list operations.
Pointer Setup: Initialize two pointers, l1 and l2, to point to the respective heads of the two lists. A current pointer is also initialized to track the end of the merged list as it grows.
Merging Process: Traverse both lists using the following logic:
- Compare the current values of l1 and l2.
- Append the smaller value to the current pointer and move the corresponding list pointer forward.
- Repeat this until one of the lists is fully traversed.
Appending Remaining Nodes: Once one list is exhausted, any remaining nodes from the other list are appended directly to the merged list.
Return the Result: The merged list starts from dummy.next, as the dummy node itself does not hold meaningful data.

Step-by-Step Example

Using the previously mentioned lists as an example:

Start with a dummy node and set current to the dummy.
Compare the first elements:
- l1 (1) ≤ l2 (1): Append l1.
- Move l1 pointer forward.
Compare the next elements:
- l1 (1) ≤ l2 (3): Append l1.
- Move l1 pointer forward.
Continue this process, appending the smaller values until all nodes are processed.

Implementation

The following code implements the above logic:

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while(l1!=null && l2!=null){
            //Merge List
            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 dummy.next;
    }
}

Complexity Analysis

Time Complexity: O(n), where n is the total number of nodes in both lists. Each node is visited exactly once.
Space Complexity: O(1), as no additional nodes are created aside from the dummy node.

Conclusion

Merging two sorted linked lists is an essential skill in algorithm design. This guide has presented a clear methodology along with an accompanying code example to demonstrate the implementation of this algorithm. Understanding this concept not only aids in mastering linked lists but also enhances problem-solving skills in data structure manipulation.

Merging Two Sorted Lists