LeetCode Python Solutions: 21. Merge Two Sorted Lists
ZeroStress LeetCode Python Solutions: 21. Merge Two Sorted Lists
#python #leetcode
Twitter: / qiaoliuciao
The intuition behind this solution is to merge two sorted linked lists by comparing the values of their nodes and creating a new linked list with the merged values. The solution takes advantage of the fact that both input lists are already sorted.
The process starts by creating a dummy node, which serves as the head of the merged list. We also initialize a current variable to keep track of the current node in the merged list.
Then, we enter a while loop that continues as long as both list1 and list2 have remaining nodes. Within the loop, we compare the values of the current nodes in list1 and list2.
If the value of the current node in list1 is less than or equal to the value of the current node in list2, we append the node from list1 to the merged list by assigning current.next to list1, and then we move the list1 pointer to the next node. This is done because the current node in list1 is smaller or equal, so it should come before the current node in list2 in the merged list.
On the other hand, if the value of the current node in list2 is smaller, we append the node from list2 to the merged list by assigning current.next to list2, and then we move the list2 pointer to the next node.
In both cases, we move the current pointer to the next node in the merged list to maintain the correct order.
The loop continues until one of the lists becomes empty, indicating that we have reached the end of one of the original lists. At this point, we append the remaining nodes from the non-empty list to the merged list by connecting the current.next pointer to the remaining nodes.
Finally, we return the head of the merged list by skipping the dummy node. The merged list is now a single linked list containing all the nodes from both input lists, merged in sorted order.
The time complexity of this solution is O(n + m), where n and m are the lengths of list1 and list2 respectively. This complexity arises because we iterate through both lists once, comparing the values of their nodes and constructing the merged list. The time complexity is linear with respect to the total number of nodes in the two lists.
The space complexity of this solution is O(1) since we only use a constant amount of extra space. We create a single dummy node and a current variable to keep track of the merged list, but these do not depend on the input size. We do not utilize any additional data structures that grow with the size of the input lists.
It's worth noting that the space complexity does not include the space required to store the output merged list itself. The space complexity only accounts for the extra space used by the algorithm, and in this case, it remains constant regardless of the input size.
The approach of this solution is a straightforward iterative approach that merges two sorted linked lists by comparing their values and creating a new sorted linked list. Here is a step-by-step breakdown of the approach:
1. Create a dummy node and initialize a current variable to keep track of the current node in the merged list.
2. Start a while loop that continues until both list1 and list2 have remaining nodes.
3. Within the loop, compare the values of the current nodes in list1 and list2.
4. If the value of the current node in list1 is less than or equal to the value of the current node in list2, append the node from list1 to the merged list by assigning current.next to list1, and move the list1 pointer to the next node.
5. If the value of the current node in list2 is smaller, append the node from list2 to the merged list by assigning current.next to list2, and move the list2 pointer to the next node.
6. In both cases, move the current pointer to the next node in the merged list to maintain the correct order.
7. Continue the loop until one of the lists becomes empty.
8. After the loop, one of the lists may still have remaining nodes. Append the remaining nodes to the merged list by connecting the current.next pointer to the non-empty list.
9. Finally, return the head of the merged list by skipping the dummy node.
The key idea of this approach is to traverse the input lists simultaneously, comparing the values of their nodes, and creating a new linked list with the merged values in sorted order. By iterating through the lists only once and linking the nodes appropriately, we efficiently construct the merged list.
00:00 Code
03:24 Main
11:30 End