The original problem

This is problem number 21 on LeetCode, look at the description of the problem on LeetCode:

Merges two ordered lists into a new ordered list and returns. A new list is formed by concatenating all the nodes of a given two lists.

Example:

Input: 1->2->4, 1->3->4

Output: 1 – > 1 – > 2 – > 3 – > 4 – > 4

It’s pretty clear what they mean. Merge two ordered lists into one ordered list and return.

Their thinking

When it comes to merge operations, it should be easy to think of merge methods after learning merge sort. If you don’t, you can refer to an article I wrote about merge sort, and you know the idea of merge, and it’s not that hard to solve this problem.

Code implementation

Notice two details

  • Whether it is necessary to create a new memory space to store the sorted nodes, the method I use does not create a new memory space, because whether it is opened or not, the time complexity is the same, is 0(n + m),n is the number of l1 nodes, m is the number of L2 nodes. How to do that without opening up new memory space? Here I am directly operating on the linked list of L1 or L2. The choice of L1 or L2 depends on the size of the header of L1 and L2. If L1 is small, I operate on L1, and if L2 is small, I operate on L2.
  • Whether to use virtual headers, if yes, there is no need to determine the size of l1 and L2 headers as the combined list headers. I’m not using it here.

See the comments in the code for an explanation.

Class Solution{public: ListNode *mergeTwoLists(ListNode *l1, ListNode *l2){if l1 == NULL, return l2.if(! l1)returnl2; // if l2 == NULL, return l1; if l1 == NULL, return l1;if(! l2)returnl1; ListNode *head; ListNode *head; ListNode *tail; // Compare L1 and L2 to determine the header to return the listif (l1->val <= l2->val) {
            head = l1;
            l1 = l1->next;
        } else{ head = l2; l2 = l2->next; } // use tail to start the merge operation tail = head; // If l1 and L2 still have nodes, then compare the size of the nodes and join the smaller ones behind the tail.while (l1 && l2) {
            if (l1->val <= l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else{ tail->next = l2; l2 = l2->next; } // end = tail->next; } // If l1 == NULL, or l2 == NULL, concatenate the remaining nodes. tail->next = l1 ? l1 :l2; // return the headerreturnhead; }};Copy the code

If you have some doubts about some leetcode topic, you can refer to under my github:github.com/xiaoswu/Lee… Above, there are some solutions to problems in LeetCode. Hope I can help you!