How LeetCode merges two ordered linked lists
This article will explain in detail how LeetCode merges two ordered linked lists. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.
Description of the topic
Merge two ascending linked lists into a new ascending linked list and return it, which is formed by splicing all nodes of a given two linked lists, such as:
Input: 1-> 2-> 4, 1-> 3-> 4 output: 1-> 1-> 2-> 3-> 4-> 4. 2. Iterative method for solving problems.
Using the loop iteration method, you can find out the smaller nodes in turn and link them together:
Comparing the current node values of L1 and L2 links the smaller node to the L3 tail L1 or L2 pointer back one bit L3 pointer back to the end of the loop: one of L1 and L2 traverses to the tail links all the untraversed nodes to the L3 tail and returns the saved L3 header pointer head- > nextclass Solution {
Public:
ListNode* mergeTwoLists (ListNode* L1, ListNode* L2) {
/ / 1. Ascending linked list L3
ListNode * L3 = new ListNode (0)
/ / 2. Save the header pointer to return the result
ListNode * head = L3
While (L1 & & L2) {
/ / 3. Select a smaller node to connect to the L3 tail
If (L1-> val val) {
L3-> next = L1
L1 = L1-> next
} else {
L3-> next = L2
L2 = L2-> next
}
L3 = L3-> next
}
/ / Link redundant L1 or L2 nodes directly to the L3 tail
L3-> next = (L1 = = nullptr? L2: L1)
Return head- > next
}
}
Complexity analysis time complexity: O (m + n), the number of cycles is equal to the total length of two linked lists m + n space complexity: O (1), the variable memory used is constant level 2.2 recursive method
Recursive methods should pay attention to recursive expressions and loop end conditions:
When L1 is empty, return L2 when L2 is empty, return l1l1 and L2 are not empty, the comparison node val links the smaller node and recursively calls the function to determine the next linked node
Recursive method is not easy to understand, it is recommended to use vs debugging to take a look at the memory.
Class Solution {
Public:
ListNode* mergeTwoLists (ListNode* L1, ListNode* L2) {
/ / 1. Recursive end condition
If (L1 = = nullptr)
Return l2
/ / 2. Recursive end condition
If (L2 = = nullptr)
Return l1
/ / 3. Recursive expression
If (L1-> val val) {
L1-> next = mergeTwoLists (L1-> next, L2)
Return l1
} else {
L2-> next = mergeTwoLists (L1, L2-> next)
Return l2
}
}
}
Complexity analysis time complexity: O (m + n), each recursion will add a linked list node, and finally recursive m + n times space complexity: in the process of recursion, all m + n nodes will be saved in the recursive call stack at once.
This is the end of the article on "how LeetCode merges two ordered linked lists". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, please share it for more people to see.
