21. Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]
 
Constraints:

The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.

题目翻译：
给定两个已排序的链表 list1 和 list2 的头结点。

将这两个链表合并为一个已排序的链表。新链表应该通过将前两个链表的节点拼接在一起形成。

返回合并后的链表的头结点。

示例 1：

输入：list1 = [1,2,4], list2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：

输入：list1 = [], list2 = []
输出：[]
示例 3：

输入：list1 = [], list2 = [0]
输出：[0]

约束：

两个链表中的节点数量都在范围 [0, 50] 内。
-100 <= Node.val <= 100
list1 和 list2 都按非递减顺序排序。

class Solution {
    // public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    //     ListNode head=new ListNode();
    //     ListNode cur=head;
    //     while(list1!=null && list2!=null){
            
    //         if(list1.val<=list2.val){
    //             cur.next=list1;
    //             list1=list1.next;  
    //         }
    //         else{
    //             cur.next=list2;
    //             list2=list2.next;
    //         }
    //         cur=cur.next;
    //     }
    //     if(list1!=null){
    //         cur.next=list1;
    //     }
    //     else{
    //         cur.next=list2;
    //     }
    //     return head.next;
    // }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
            if(list1==null) return list2;
            if(list2==null) return list1;
            if(list1.val>list2.val){
                ListNode temp=list1;
                list1=list2;
                list2=temp;
            }

            ListNode res=list1;
            while(list1!=null && list2!=null){
                ListNode temp=null;
                while(list1!=null && list1.val<=list2.val){
                    temp=list1;
                    list1=list1.next;
                }
                temp.next=list2;

                ListNode swap=list1;
                list1=list2;
                list2=swap;

            }
            return res;
    }
}