Subject to introduce

Force buckle 21: leetcode-cn.com/problems/me…

Analysis of the

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 code is as follows:

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; }} * * /
class Solution {
    
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // Sentry node, which points to the element above the head node of the merged list
        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;

        while(l1 ! =null&& l2 ! =null) {
            // Compare the sizes
            if(l1.val < l2.val) {
                prev.next = l1;
                l1 = l1.next;
            }else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // If l1 has not been traversed, add the remaining elements of L1 directly to the end of the new list
        if(l1 ! =null) {
           prev.next = l1; 
        }

        // If L2 has not been traversed, add the remaining elements of L2 directly to the end of the new list
        if(l2 ! =null) {
           prev.next = l2; 
        }
        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 only one element of L1 and L2 is added to the combined list in each iteration of the loop, the number of while loops cannot exceed the sum of the lengths 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.