This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

Merges two sorted lists

Enter two incrementally sorted lists and merge them so that the nodes in the new list are still incrementally sorted.

Example 1:

Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4Copy the code

limit

0 <= List length <= 1000

Thought analysis

Since the list is already sorted, we should compare the values of the two lists one by one. The values less than are ranked first, the values greater than are ranked last, and then join the remaining lists together.

The code shown

Time complexity is O(n){O(n)}O(n), space complexity is O(1){O(1)}O(1).

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode p = new ListNode();
        ListNode prev = p;
        while(l1 ! =null&& l2 ! =null) {if(l1.val >= l2.val){
                p.next = l2;
                l2 = l2.next;
            } else {
                p.next = l1;
                l1 = l1.next;
            }
            p = p.next;
        }
        if(l2 == null){
            p.next = l1;
        }
        if(l1 == null){
            p.next = l2;
        }
        return prev.next;
    }
Copy the code

conclusion

The thing to remember in this case is don’t forget to join the rest of the list together.