[sword finger offer] interview question 25 Merge two ordered linked lists

Interview questions 25. Merge two ordered lists

subject

Enter two ascending ordered linked lists , Merge these two linked lists and make the nodes in the new linked list still be sorted incrementally .

Ideas

• Set up dummy Is an empty node , As a new linked list , So the last thing back is dummy.next, Set up cur Is the current node , from dummy Start
• Both linked lists are non empty as a loop condition , Select the smaller nodes in two linked lists at a time , The corresponding linked list node moves back one bit
• After each cycle cur Also move back one bit , If after the cycle ends , The list is not empty , take cur Point to non empty linked list
• Last , return dummy.next

Code

/** * 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) {
    
        ListNode dummy = new ListNode();//  Define a dummy node 
        ListNode cur = dummy;

        while(l1 != null && l2 != null)
        {
    
            //  Select a smaller node value each time 
            if(l1.val <= l2.val)
            {
    
                cur.next = l1;
                l1 = l1.next;
            }
            else
            {
    
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }

        //  If the nodes of a linked list are not merged , Then merge all the nodes in the linked list into the new linked list 
        if(l1 != null)
        {
    
            cur.next = l1;
        }
        
        if(l2 != null)
        {
    
            cur.next = l2;
        }

        return dummy.next;
    }
}