This is the 18th day of my participation in Gwen Challenge

preface

The combination of two ordered linked lists is shown as follows:

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.

Example 1:

Input: l1 = [1,2,4], l2 = [1,3,4]

Example 2:

Input: L1 = [], L2 = [] output: []

Example 3:

Input: L1 = [], L2 = [0] output: [0]

A, thinking

Since you are merging two ascending lists, it is natural to think of using iteration to merge. The general idea is to insert smaller values from L1 and L2 into the new list while traversing L1. If L2 is not empty at the end of L1 traversal, the whole of L2 is inserted into the new list.

Take a look at the steps, using l1 = [1,2,4] and L2 = [1,3,4] in example 1.

Hear1: points to the head of L1. Head2: points to the head of L2

The illustration

The initial state is as follows:

If the first element 1 in L1 is not less than 1 in L2, the element in L2 is selected and head2 is moved back one bit. As shown below:

Elements 1 and 2 after L1 are smaller than elements 3 in L2, so elements 2 and 3 in L1 are added to the new list. As shown below:

The element 4 after L1 is not less than 3 and 4 in L2, so 3 and 4 in L2 are added to the new list. As shown below:

Finally, the last element in L1, 4, is added to the new list. As shown below:

I believe that through the above step analysis, very clear can know how to merge the ordered list through iteration!

Second, the implementation

Code implementation

Ret: temp: temp: temp: temp: temp: temp: temp: temp: temp: temp: temp: temp: temp

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode ret = new ListNode();
        ListNode temp = ret;
        / / iteration
        while(l1 ! =null&& l2 ! =null) {
            if (l1.val < l2.val) {
                temp.next = new ListNode(l1.val);
                l1 = l1.next;
            } else {
                temp.next = new ListNode(l2.val);
                l2 = l2.next;
            }
            temp = temp.next;
        }
        // Categorize untraversed lists into results
        if (l1 == null) {
            temp.next = l2;
        }
        if (l2 == null)
            temp.next = l1;
        return ret.next;
    }
Copy the code

The test code

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1.new ListNode(2.new ListNode(4)));
        ListNode l2 = new ListNode(1.new ListNode(3.new ListNode(4)));
        new Number21().mergeTwoLists(l1, l2);
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥