合并有序链表

21.合并两个有序链表

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode pre = dummy;
        while(list1!=null&&list2!=null){
            if(list1.val < list2.val){
                ListNode node = new ListNode(list1.val);
                pre.next = node;
                list1 = list1.next;
            }else {
                ListNode node = new ListNode(list2.val);
                pre.next = node;
                list2 = list2.next;
            }
            pre = pre.next;
        }
        pre.next = list1!=null?list1:list2;
        return dummy.next;
    }
}

// 追问：递归实现？
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        else if(list2 == null) return list1;
        else if(list1.val <= list2.val){
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }else{
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}


// 面试追问，去重呢？
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode pre = dummy;
        while(list1!=null&&list2!=null){
            if(list1.val < list2.val){
                ListNode node = new ListNode(list1.val);
                pre.next = node;
                list1 = list1.next;
            }else if(list1.val > list2.val){
                ListNode node = new ListNode(list2.val);
                pre.next = node;
                list2 = list2.next;
            } else {
                 ListNode node = new ListNode(list1.val);
                 pre.next = node;
                 list1 = list1.next;
                 list2 = list2.next;
            }
            pre = pre.next;
        }
        pre.next = list1!=null?list1:list2;
        return dummy.next;
    }
}

K个链表合并----分治（归并排序）或者优先队列（堆排序）easy略