This is the 9th day of my participation in the November Gwen Challenge. See details: The Last Gwen Challenge 2021.

Topic describes

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

Their thinking

According to the description of the problem, given that two lists are themselves ordered, we need to merge them into one ordered list, that is, we need to join the two lists together and reorder them to get the final result. I provide two solutions for this problem, the non-recursive solution and the recursive solution.

Non-recursive solution

Implement a single linked list (ListNode) :

public class ListNode<E> {
    public ListNode next;
    public E e;
​
    public ListNode(E e) {
        this(e, null);
    }
​
    public ListNode(E e, ListNode next) {
        this.e = e;
        this.next = next;
    }
​
​
    public ListNode() {
        this(null, null);
    }
Copy the code

Non-recursive code

public class MergeList { public static void main(String[] args) { MergeList mergeList = new MergeList(); ListNode node1 = new ListNode(1); ListNode node11 = new ListNode(3); node1.next = node11; node11.next = node111; ListNode node2 = new ListNode(2); ListNode node22 = new ListNode(4); ListNode node222 = new ListNode(6); node2.next = node22; node22.next = node222; ListNode node = mergeList.mergeTwoLists(node1, node2); } public ListNode mergeTwoLists(ListNode<Integer> l1, ListNode<Integer> l2) {// Set dummy head node ListNode<Integer> dummy = new ListNode<Integer>(0), pp = dummy; while (l1 ! = null && l2 ! = null) { if (l1.e <= l2.e) { pp.next = l1; pp = pp.next; l1 = l1.next; } else { pp.next = l2; pp = pp.next; l2 = l2.next; } } if (l1 ! = null) { pp.next = l1; } if (l2 ! = null) { pp.next = l2; } return dummy.next; }}Copy the code

The general idea of non-recursive solution is to compare the values of L1 and L2 linked lists one by one through the while loop. Assuming that the value of L1 is the smallest in the first round of comparison, put L1 into the result linked list, and then move L1 to the next place. The two continue to compare, and so on. When one of them is empty, it jumps out of the loop. After the loop, because one of them must still have a value, it directly points the next node of the current result list node to the non-empty list. Finally, it gets the sorted result and returns it.

To demonstrate this with a dynamic diagram:

The recursive method

/** @param l1 * @param l2 * @return */ public ListNode mergeTwoLists(ListNode<Integer> l1, ListNode<Integer> l2) { if (l1 == null) { return l2; } else if (l2 == null) { return l1; } else if (l1.e < l2.e) { l1.next = mergeTwoList(l1.next, l2); return l1; } else { l2.next = mergeTwoList(l1, l2.next); return l2; }}Copy the code

The termination condition for recursion is that if one of the two lists l1 and L2 is empty it terminates and then goes back up and returns the answer.

So how do I recurse?

We determine which l1 or L2 head node is smaller, and then we point the next pointer of the smaller node to the result of the merge of the remaining nodes, simply continuing to call the recursive method until the termination condition is satisfied.

The recursion code is very concise, but it can look very convoluted. Layer by layer recursion can easily get confused if you are not careful. Let’s break down the recursion and analyze it step by step:

L1 is 1->3, L2 is 2->4->6

First method call:

The first node of L1 is 1 and l2 is 3, so l1.next points to the next method call

Next =mergeTwoList

  l1.next = mergeTwoList(l1.next, l2);
            return l1;
Copy the code

Second method call:

Compare the second node in L1 to the head node in L2

3 is larger than 2, so L1.next is the head node of L2

 l2.next = mergeTwoList(l1, l2.next);
            return l2;
Copy the code

L1 -> l2-> l2.next=mergeTwoList

The third method call compares the second node of L2 with the second node of L1:

4 is larger than 3, so l2’s next node is the second node in L1

Next ->l1.next. Next = mergeTwoList

Fourth method call:

At this time, L1 has no third node, so the current node of L1 is empty and it starts to backtrack upward:

So the empty node in L1 is the second node in L2

Result list: L1 -> L2 -> l1.next -> l2.next

Then the final value is: 1->2->3->4->6

conclusion

Two solutions, the second recursive solution may be difficult to understand, my suggestion is step by step debug, see the value change, step by step tracking, you can thoroughly understand, here to give you a question, if it is multiple ordered linked lists to merge, how should we operate? Pay attention to me, the next article for you to answer.