Merge two sorted Linked List (use method used in mergeSort)

Problem Overview

In the problem "Merge Two Sorted Lists," we are tasked with merging two sorted linked lists into a single sorted linked list. The two input linked lists are individually sorted, and the goal is to merge them in such a way that the resulting linked list also stays sorted.

Link to problem: Merge Two Sorted Lists

Understanding the Problem

Given two sorted linked lists, we should combine them into one sorted linked list. The resulting list should maintain the order provided by the initial two lists. The task is to ensure that the elements in the final list are in ascending order, and all elements from both lists are included.

Input

• Two linked lists, l1 and l2, where each node contains a single integer value.

Output

• A single linked list, which is the result of merging the input lists while maintaining the sorted order.

Example

Example 1:

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

Example 2:

• Input: l1 = [], l2 = []
• Output: []

Example 3:

• Input: l1 = [], l2 = [0]
• Output: [0]

Key DSA Concepts and Theory

Linked List Basics

• Linked List is a linear data structure where elements are stored in nodes. Each node contains data and a reference to the next node in the sequence. This makes operations like insertion and deletion easier than arrays.

Understanding Merging

• Merging Two Sorted Lists is an operation where we selectively pick elements from each list to form a new list while keeping the resultant list sorted. It utilizes the fact that both input lists are already sorted.

Solution Approach

The approach involves iteratively comparing the head nodes of both lists and including the smaller value node into our merged list.

Steps:

1. Initialize a Dummy Node: Create a dummy node to serve as the head of the new linked list. This will help us easily return the head of the merged list at the end.

2. Use Two Pointers: Maintain two pointers to traverse the two lists (l1 and l2).

3. Iterate and Compare:

   • While both l1 and l2 have not reached the end:
     • Compare the val of nodes pointed by the pointers.
     • Append the smaller node to the merged list and move the pointer.

4. Handle Remaining Nodes: Once you've exhausted one list, simply attach the remaining part of the other list to the end of the merged list.

5. Return: Return the node next to the dummy as it serves as the head of the newly merged list.

Code (C++)

class ListNode {
public:
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        
        tail->next = l1 ? l1 : l2;
        
        return dummy.next;
    }
};

Code (Java)

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

class Solution {
    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;
    }
}

Time and Space Complexity Analysis

Time Complexity

• O(n + m): where n and m are the lengths of two lists. Each node from both lists is visited once, resulting in linear time complexity.

Space Complexity

• O(1): The algorithm uses constant space as no additional data structure is used beyond a few pointers.

Common Mistakes to Avoid

1. Forgetting to Attach Remaining Nodes:

   • Ensure the remaining part of the list is attached to the merged list after one becomes null.

2. Misplaced Conditions:

   • Ensure that condition checks correctly compare node values to maintain sorted order.

Similar Problems on LeetCode

1. No. 23 - Merge k Sorted Lists
2. No. 21 - Merge Two Sorted Lists
3. No. 148 - Sort List

Additional Resources and References

• Wikipedia on Linked Lists
• GeeksforGeeks - Linked List Introduction

Understanding this foundational concept of merging two sorted linked lists can greatly enhance your problem-solving ability in dealing with similar problems on linked data structures. It is a crucial step toward grasping more complex operations and algorithms in linked lists and other data structures.