describe

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

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

Train of thought

Combine two lists into a single list using a loop loop. Each merge is preceded by a comparison operation.

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; }} * * /
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // Use -1 as the head node to return the next node in the list
        ListNode out = new ListNode(-1);
        ListNode cur = out;
        while(l1 ! =null&& l2 ! =null) {// Compare and create nodes to join the list
            ListNode new_node;
            if(l1.val < l2.val){
                new_node = new ListNode(l1.val);
                l1 = l1.next;
            }else{
                new_node = new ListNode(l2.val);
                l2 = l2.next;
            }
            cur.next = new_node;
            cur = cur.next;
        }
        // Concatenate the remaining nodes at the end of the list
        if(l1 ! =null){
            cur.next = l1;
        }else{
            cur.next = l2;
        }
        returnout.next; }}Copy the code
Given in the Java online submissions with Merge Two Sorted Lists.
Memory Usage: 39.3 MB, less than 17.51% of Java online submissions for Merge Two Sorted Lists.

Another way to think about it

Using the recursive method, the two linked lists are combined.

But recursion makes the program less efficient.

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2){
        // If one list is empty, join another list
        if(l1 == null) return l2;
	if(l2 == null) return l1;
        // Otherwise, join the smaller list recursively
	if(l1.val < l2.val){
	    l1.next = mergeTwoLists(l1.next, l2);
	    return l1;
	} else{
	    l2.next = mergeTwoLists(l1, l2.next);
	    returnl2; }}}Copy the code
Given in the Java online submissions with Merge Two Sorted Lists.
Memory Usage: 39.3 MB, less than 17.51% of Java online submissions for Merge Two Sorted Lists.