Leetcode LinkedList

21. Merge Two Sorted Lists Easy

Link : https://leetcode.com/problems/merge-two-sorted-lists/

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

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

Optimized solution in C++:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     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* list1, ListNode* list2) {
        ListNode* res = new ListNode(-1);
        ListNode* ans = res;
        while(list1 && list2){
            if(list1->val <= list2->val){
                ans->next= new ListNode(list1->val);
                list1= list1->next;
            }
            else{
                ans->next= new ListNode(list2->val);
                list2= list2->next;
            }
            ans= ans->next;
        }
        if(list1){
            ans->next= list1;
        }
        if(list2){
            ans->next= list2;
        }
        return res->next;
    }
};

Solution Explanation:

Merging Two Sorted Lists

This solution is about combining two sorted lists (let's call them list1 and list2) into one single sorted list. Imagine you have two lines of people, each line is ordered by height. You want to form a new line that keeps everyone in order of height, pulling the shortest person available from the front of either line each time.

How It Works

1. Creating a Starting Point: First, we create an imaginary person (or a temporary starting node) that stands before the new line starts forming. This helps us easily add people to the new line without worrying about who is first.

2. Comparing Heights (Values): We look at the first person in each line. Whichever person is shorter (or if they're the same height, it doesn't matter which one we choose), we add them to the end of the new line and then step forward in the line they came from.

3. Repeating the Process: We keep doing this - comparing the first person in each line, adding the shorter one to the new line, and stepping forward in their line. If one line runs out of people, we simply add the rest of the people from the other line to the end of the new line.

4. Final Step: After we've gone through both lines entirely, our new line is complete. But remember the imaginary person we placed at the start? They're not actually part of the new line, so we make sure the new line starts with the first real person we added.

Technical Explanation

• A new list node (res) with a value of -1 is created to act as the starting point. The ans pointer is used to add new nodes to the list.
• As long as there are elements in both list1 and list2, we compare their values.
  • If list1's value is less than or equal to list2's, we add list1's value to the new list and move list1 forward.
  • Otherwise, we add list2's value and move list2 forward.
• If we reach the end of one list, we connect the remaining elements of the other list directly to the new list.
• Finally, since the first node (-1) was just a placeholder, we return the list starting from the next node, which is the actual start of our merged list.

This solution effectively merges two sorted lists into one, maintaining the sorted order, with a time complexity that is linear to the combined length of the two lists.