Analysis of the

Method one: recursion

Train of thought

We can recursively define the merge operation in two lists (ignoring boundary cases such as empty lists, etc.) as follows:

$\left{ \begin{array}{ll} list1[0] + merge(list1[1:], list2) & list1[0] < list2[0] \ list2[0] + merge(list1, list2[1:]) & otherwise \end{array} \right. $

That is, the smaller of the two linked list headers is merged with the result of the remaining element merge operation.

algorithm

We directly model the above recursive process, taking into account the boundary cases.

If L1 or L2 is an empty list to begin with, then no operations need to be merged, so we just need to return a non-empty list. Otherwise, we need to determine which of the list’s first nodes has a smaller value, L1 or L2, and recursively decide which node to add to the result next. If either list is empty, the recursion ends.

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        else if (l2 == null) {
            return l1;
        }
        else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            returnl2; }}}Copy the code

Complexity analysis

  • Time complexity: O(n + m), where n and M are the lengths of two linked lists respectively. Because every time I call it, the recursion gets removedl1orl2The head node of the function (until at least one list is empty)mergeTwoListEach node is called recursively at most once. Therefore, the time complexity depends on the length of the merged list, O(n+m).
  • Space complexity: O(n + m), where n and M are the lengths of two linked lists respectively. Recursive callsmergeTwoListsFunction consumes stack space, which depends on the depth of the recursive call. End the recursive callmergeTwoListsThe function is called at most n+m times, so the space complexity is O(n+m).

Method two: iteration

Train of thought

We can use iterative method to implement the above algorithm. When both L1 and L2 are not empty linked lists, judge which of the first nodes in l1 and L2 has a smaller value, and add the node with the smaller value to the result. When a node is added to the result, move the node in the corresponding linked list one bit later.

algorithm

First, we set up a sentinel node, prehead, which makes it easier to return to the merged list at the end. We maintain a prev pointer, and all we need to do is adjust its next pointer. We then repeat the process until l1 or L2 points to NULL: if l1’s current value is less than or equal to L2, we append l1’s current value to prev and move l1’s pointer back one bit. Otherwise, we do the same for L2. Regardless of which element we appending, we need to move the prev one bit back.

At the end of the loop, at most one of L1 and L2 is non-null. Since both input lists are ordered, no matter which list is non-empty, it contains all the elements larger than all of the previously merged lists. This means that we simply appending the non-empty list to the merged list and return the merged list.

The following figure shows the process of iteratively merging 1->4->5 and 1->2->3->6 lists:

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while(l1 ! =null&& l2 ! =null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // At most one of l1 and L2 has not been merged, we can directly point to the end of the unmerged list
        prev.next = l1 == null ? l2 : l1;

        returnprehead.next; }}Copy the code

Complexity analysis

  • Time complexity: O(n + m), where n and M are the lengths of two linked lists respectively. Because each iteration of the loop,l1 和 l2Only one element will be put into the merged list, sowhileThe number of loops cannot exceed the sum of the two lists. The time complexity of all other operations is constant, so the total time complexity is O(n+m).

    In the generation,l1 和 l2Only one element will be put into the merged list, sowhileThe number of loops cannot exceed the sum of the two lists. The time complexity of all other operations is constant, so the total time complexity is O(n+m).
  • Space complexity: O(1). We just need constant space for a number of variables.