Shulou(Shulou.com)06/01 Report--

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.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.