21Merge Two Sorted Lists

21Merge Two Sorted Lists

**最直接的算法**

是新建一个表头，然后同时访问两条list，不断把表头上比较小的node摘下来挂在新表后面，直到任意一个表访问结束，然后将剩余的list挂在新表后面。

还可以用

**递归**

来做

在看这道题之前，我首先复习一下

**归并排序**

（merge sort）

static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, result, start1, end1);
    merge_sort_recursive(arr, result, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        result[k++] = arr[start1++];
    while (start2 <= end2)
        result[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = result[k];
}
public static void merge_sort(int[] arr) {
    int len = arr.length;
    int[] result = new int[len];
    merge_sort_recursive(arr, result, 0, len - 1);
}

这道题的思路和这个差不多，分成一半一半然后merge two 。

 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                cur.next = l1;
                l1=l1.next;
            }else{
                cur.next = l2;
                l2=l2.next;
            }
            cur=cur.next;
        }

        if(l1==null){
            cur.next = l2;
        }else{
            cur.next = l1;
        }
        return dummy.next;
    }

    public ListNode helper(ListNode[] lists, int start, int end){
        if (start>=end) return lists[start];

        int mid = (start+end)/2;
        ListNode l1 = helper(lists, start,mid);
        ListNode l2 = helper (lists,mid+1,end);
        return mergeTwoLists(l1,l2);
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0)return null;
        if(lists.length==1) return lists[0];
        return helper(lists,0,lists.length-1);

    }