【LeetCode - Java】21. Merge two ordered linked lists (simple)

1. Title Description

2. Their thinking

This kind of topic belongs to classic data structure Class title , understand Linked list After the feature, it's good to start . First Conventional thinking There are two kinds of , One is Make elements in a list Insert To another linked list to form an ordered linked list that meets the requirements ; another The train of thought is Generate a new linked list , Put the elements that meet the requirements in the two old linked lists add to To the new linked list .

Plug in processing relative Generative expressions are a little more troublesome , You need to determine Which old linked list to use as the benchmark , According to the requirements of this topic, you should choose Small opening element The linked list is used as the insertion benchmark , Before that, we need to Judge not empty , Otherwise it will appear Null pointer exception .

in addition to , This topic can also be based on recursive The mind of . Recursive function Is to find out At present Nodal Elements as well as The subsequent Of Sublist , This kind of thinking is actually Be similar to Plug in processing ideas .

3. Code implementation

3.1 Plug in

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    
        ListNode pre;
        ListNode list;
        if(list1==null)
            return list2;
        else if(list2==null)
            return list1;
        else if (list1.val < list2.val) {
    
            list = list1;
            list1 = list1.next;
        } else {
    
            list = list2;
            list2 = list2.next;
        }
        pre = list;
        while (list1 != null && list2 != null) {
    
            if (list1.val < list2.val) {
    
                pre.next = list1;
                list1 = list1.next;
            } else {
    
                pre.next = list2;
                list2 = list2.next;
            }
            pre = pre.next;
        }
        pre.next = list1 == null ? list2 : list1;
        return list;
    }

3.2 Generative

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    
        ListNode pre;
        ListNode list = new ListNode();
        pre = list;
        while (list1 != null && list2 != null) {
    
            if (list1.val < list2.val) {
    
                pre.next = list1;
                list1 = list1.next;
            } else {
    
                pre.next = list2;
                list2 = list2.next;
            }
            pre = pre.next;
        }
        pre.next = list1 == null ? list2 : list1;
        return list.next;
    }

3.3 Recursive

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    
        if (list1 == null)
            return list2;
        else if (list2 == null)
            return list1;
        else {
    
            if (list1.val < list2.val) {
    
                list1.next = mergeTwoLists(list1.next, list2);
                return list1;
            } else {
    
                list2.next = mergeTwoLists(list1, list2.next);
                return list2;
            }
        }
    }

This implementation is the subject Relatively optimal performance Solution method .

3.4 contrast

Of the above three methods Time complexity All are O(m+n),m and n They are the of two linked lists length , Therefore, the time performance of the three algorithms There is no difference . And in the Spatial complexity On , Generative algorithm because it needs to generate New linked list , Therefore, compared with other algorithms in terms of space occupation Bigger . Recursive Although the solution is feasible in this subject , Because the number of nodes in this topic does not exceed 50, But if the number of nodes is too large Prone to stack overflow The situation of .