题解 | #合并两个排序的链表#

public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        
        if (list1 == null) return list2 ;
        if (list2 == null) return list1 ;
        
        ListNode dummary = new ListNode(0);
        ListNode cur = dummary;
        int l1 ,l2;
        while(list1 != null && list2!=null){
            
            if (list1.val <= list2.val){
                cur.next = list1;
                cur = cur.next ;
                list1 = list1.next;
            }else{
                cur.next = list2 ;
                cur = cur.next ;
                list2 = list2.next ;
            }
            
        };
        
        if(list1 != null ){
            while (list1 != null){
                cur.next =list1;
                cur = cur.next;
                list1 = list1.next;
            };
        }
        
        if(list2 != null ){
            while (list2 != null){
                cur.next =list2;
                cur = cur.next;
                list2 = list2.next;
            };
        }
        return dummary.next;
        
    }
}

1、首先判断链表是否为空链表，如果其中一个为空链表，则返回另外一个链表； 2、如果都不是空链表，那就开始比较，但是比较前，需要创建一个哨兵节点dummary，用来返回结果，另外一个cur节点，用来存储遍历的结果 3、对链表开始遍历：先比较两个链表的值，对于小的值，就让cur的下一个指针指向它，并让cur等于cur的下一个指针，直到其中一个为空； 4、等其中一个链表为空后，就让cur的下个指针去接上去那个非空的链表就行了。 时间复杂度为O(n),空间复杂度也为O(n)。