grid47 Exploring patterns and algorithms
Nov 4, 2024
5 min read
Solution to LeetCode 21: Merge Two Sorted Lists Problem
Given two sorted linked lists, merge them into one sorted linked list by splicing together the nodes from both lists. Return the head of the merged linked list.
Problem
Approach
Steps
Complexity
Input: You are given two sorted linked lists, list1 and list2. Each list is sorted in non-decreasing order and contains a series of nodes.
Example: list1 = [5,10,15], list2 = [1,7,12]
Constraints:
• The number of nodes in each list is between 0 and 50.
• -100 <= Node.val <= 100
• Both lists are sorted in non-decreasing order.
Output: Return the head of the new sorted linked list formed by merging the two input lists.
Example: Output: [1,5,7,10,12,15]
Constraints:
Goal: Merge two sorted linked lists into a single sorted list.
Steps:
• Initialize a dummy node to help with list manipulation.
• Use two pointers to traverse through both linked lists, comparing nodes at each step.
• Append the smaller node to the result list and move the corresponding pointer.
• After one of the lists is exhausted, append the remaining nodes from the other list.
Goal: The constraints ensure that the input lists are within reasonable bounds for processing.
Steps:
• The number of nodes in each list is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.
Assumptions:
• The input lists are sorted in non-decreasing order.
• There are no cycles in the linked lists.
• Input: Example 1
• Explanation: In this example, the lists [5,10,15] and [1,7,12] are merged to form the sorted list [1,5,7,10,12,15].
• Input: Example 2
• Explanation: When one of the lists is empty, as in the case of list1 = [] and list2 = [3,8], the result is just the other list: [3,8].
Approach: The approach to solving this problem is based on merging two sorted linked lists efficiently using a two-pointer technique.
Observations:
• Both input lists are sorted, which makes it easy to merge them in a single pass using two pointers.
• We can iterate through both lists, comparing the current nodes and appending the smaller one to the result list.
Steps:
• Create a dummy node to facilitate easier list manipulation.
• Use two pointers, one for each list, to compare the current nodes.
• Append the smaller node to the merged list and move the corresponding pointer.
• Once one list is exhausted, append the rest of the nodes from the other list.
Empty Inputs:
• If one or both lists are empty, return the non-empty list or an empty list if both are empty.
Large Inputs:
• Handle cases where both lists are relatively large (up to 50 nodes).
Special Values:
• Consider negative values and repeated elements in the lists.
Constraints:
• The algorithm must handle the merging process efficiently for the given constraints.
This line declares a function named 'mergeTwoLists' that takes two pointers to the heads of two sorted linked lists, 'l1' and 'l2', as input and returns a pointer to the head of the merged linked list.
2 : Base Case
if(l1 ==NULL) return l2;
This line checks if the first list 'l1' is empty. If it is, the second list 'l2' is returned directly, as it is already sorted.
3 : Base Case
if(l2 ==NULL) return l1;
This line checks if the second list 'l2' is empty. If it is, the first list 'l1' is returned directly, as it is already sorted.
4 : Condition Check
if(l1->val < l2->val) {
This line checks if the value of the current node in 'l1' is smaller than the value of the current node in 'l2'.
5 : Recursive Call
l1->next = mergeTwoLists(l1->next, l2);
If the value of the current node in 'l1' is smaller, the 'next' pointer of 'l1' is set to the result of merging the rest of 'l1' with 'l2'. This recursively merges the remaining nodes.
6 : Return
return l1;
The head of the merged list is returned, which is the original head of 'l1'.
7 : Recursive Call
l2->next = mergeTwoLists(l1, l2->next);
If the value of the current node in 'l2' is smaller or equal, the 'next' pointer of 'l2' is set to the result of merging 'l1' with the rest of 'l2'. This recursively merges the remaining nodes.
8 : Return
return l2;
The head of the merged list is returned, which is the original head of 'l2'.
Best Case: O(m + n)
Average Case: O(m + n)
Worst Case: O(m + n)
Description: The time complexity is linear in terms of the total number of nodes in both lists (m + n), as we process each node once.
Best Case: O(1)
Worst Case: O(m + n)
Description: The space complexity is O(m + n) if we count the space for the merged list, otherwise it is O(1) for the in-place merging algorithm.
