LeetCode Merge Two Sorted Lists (021

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

Another way to think about it

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