// @Title: 合并两个有序链表 (Merge Two Sorted Lists)
// @Author: qisiii
// @Date: 2022-03-10 22:24:18
// @Runtime: 0 ms
// @Memory: 40.7 MB
// @comment: 递归
// @flag: BLUE
/**
 * 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 list1, ListNode list2) {
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        ListNode result;
        if(list1.val<list2.val){
            result=list1;
            result.next=mergeTwoLists(list1.next,list2);
        }else{
            result=list2;
            result.next=mergeTwoLists(list1,list2.next);
        }
        return result;
    }
}

// @Title: 合并两个有序链表 (Merge Two Sorted Lists)
// @Author: qisiii
// @Date: 2024-04-12 23:57:16
// @Runtime: 0 ms
// @Memory: 41.6 MB
// @comment: 
// @flag: 
/**
 * 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 list1, ListNode list2) {
        ListNode result=new ListNode(-1),ans=result;
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                ans.next=new ListNode(list1.val);
                ans=ans.next;
                list1=list1.next;
            }else{
               ans.next=new ListNode(list2.val);
                ans=ans.next;
                list2=list2.next; 
            }
        }
        if(list1==null){
            ans.next=list2;
        }else{
            ans.next=list1;
        }
        return result.next;
    }
}