Leetcode: 21. Merge Two Sorted Lists (Iterative Method)

Merging Two Linked Lists - Code Explanation

In this blog post, we will explain the code for merging two singly-linked lists in C++. We will also analyze the complexity of the code and provide an example to demonstrate its usage.

Code Explanation

    <!--
    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* prehead = new ListNode(-1); 
            ListNode* prev = prehead; 

            while( list1 && list2)
            {
                if( list1->val <= list2->val)
                {
                    prev->next = list1;
                    prev = prev->next;
                    list1 = list1->next; 
                }
                else
                {
                    prev->next = list2;
                    prev = prev->next;
                    list2 = list2->next; 
                }
            }
            prev->next = list1 != nullptr ? list1 : list2;
            return prehead->next;
        }
    };

The given code defines a class named "Solution" that contains a function named "mergeTwoLists". This function takes two parameters, "list1" and "list2", which are the heads of the two singly-linked lists to be merged.

The code uses a dummy node called "prehead" to simplify the merging process. It initializes a new ListNode with a value of -1 and sets it as the prehead. This prehead will help in keeping track of the merged list.

Another pointer called "prev" is initialized to point to the prehead. It will be used to traverse the merged list and append the nodes from list1 and list2 in the correct order.

The merging process is performed using a while loop that runs as long as both list1 and list2 have nodes remaining. Inside the loop, the code compares the values of the current nodes in list1 and list2. If the value in list1 is less than or equal to the value in list2, the current node from list1 is appended to the merged list, and the pointers are updated accordingly. Otherwise, the current node from list2 is appended, and the pointers are updated.

After the while loop completes, there might be some remaining nodes in either list1 or list2. The code appends the remaining nodes to the merged list by checking if either list1 or list2 is not null. The next pointer of the "prev" node is set to the remaining nodes, effectively merging the remaining list with the merged list.

Finally, the function returns the next pointer of the prehead, which points to the head of the merged list.

Complexity Analysis

The time complexity of this code is O(n), where n is the total number of nodes in both lists. This is because the code traverses each node exactly once during the merging process.