Merge sorted linkedlist

Leave a comment

November 7, 2016 by oneOokay

  • Merge Two Sorted Lists
  • Merge k Sorted Lists

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.


用recursion写出来啦!hiahiahia

Recursive:
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
 if (l1 == null && l2 == null) return null;
 if (l1 == null) return l2;
 if (l2 == null) return l1;
 if (l1.val < l2.val){
 l1.next = mergeTwoLists(l1.next, l2);
 return l1;
 }else {
 l2.next = mergeTwoLists(l1, l2.next);
 return l2;
 }
Iterative:
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        //头不确定,引入dummy,同时引入pre来连接下一个node
        ListNode dummy = new ListNode(-1);
        ListNode pre = dummy;
        while (l1 != null && l2!= null){
            if (l1.val < l2.val){
                pre.next = l1;
                pre = l1;
                l1 = l1.next;
            }else {
                pre.next = l2;
                pre = l2;
                l2 = l2.next;
            }
        }
        if (l1 != null) pre.next = l1;
        if (l2 != null) pre.next = l2;
        return dummy.next;
    }

Merge k sorted List

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.


  • Priority Queue:一个size为lists.length的PriorityQueue。(这里不用customer class来存pop出来的点是lists中第几个出来的,因为ListNode自身的next性质就能够直接连接下一个元素了)
    • 要注意写comparator的方法。
    • TimeComplexity:O(Nlogk):k为priority queue的size,N为总的listnode的个数。每个node进出queue一次。
    • 这个可能会存在内存爆的问题,如果lists.length很大的话。
  • Divide and Conquer: recursive的二分法,也是mergeSort。
    • helper(lists, start, end, lists)
    • TimeComplexity: MergeSort的time complexity是:O(nlogn)n为要merge的元素的个数。所以这里应该是O(klogk)。再加上假设每个list最多含有n个listnode的话,总的就是O(nklogk).这样和PriorityQueue是一样的时间复杂度。
  • Merge 2 by 2:
    • 每两个两个merge。
      • 算是MergeSort的一种。时间复杂度和mergesort一样。
      • 注意他的头尾指针的写法和如何把merge的result也放到原来的list里面
    •  两个两个merge,前两个merge的结果和下一个list进行merge。TLE
      • 写法方面很好的是:
        • 用一个cur=null
        • for int i = 0; cur.next = merge(cur, lists[i])
        • 避免了处理第一次merge第一个第二个list,之后merge第n个和前面merge结果这种特殊例子。
      • 空间复杂度为O(1)
      • 时间复杂度为:
        • 第一次merge:第一个和第二个list,耗时2n(假设每个list有n的node)
        • 第二次merge:第一次merge的结果(一共2n个node)和第三个list(n个node)所以一共是3n
        • 以此类推:2n + 3n + 4n + … + (k-1) n = O(nk^2)
        • 容易超时。
PriorityQueue:
public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        Queue queue = new PriorityQueue(lists.length, new Comparator(){
            public int compare(ListNode n1, ListNode n2){
                return n1.val - n2.val;
                }});
        for (int i = 0; i < lists.length; i ++){
            if (lists[i] == null) continue;
            queue.offer(lists[i]);
        }
        ListNode dummy = new ListNode(-1);
        ListNode pre = dummy;
        while (!queue.isEmpty()){
            ListNode n = queue.poll();
            pre.next = n;
            pre = pre.next;
            if (n.next != null){
                queue.offer(n.next);
            }
        }
        return dummy.next;
    }
MergeSort:    
public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return helper(lists, 0, lists.length - 1);
    }
    
    public ListNode helper(ListNode[] lists, int start, int end){
        if (start < end){
            int mid = start + (end - start) / 2;
            return mergeTwoLists
(helper(lists, start, mid), helper(lists, mid + 1, end));
        }
        return lists[start];
    }
Merge2X2: 每两个两个merge,相当于mergesort的一种。
public ListNode mergeKLists(ListNode[] lists) {
 if (lists == null || lists.length == 0) return null;
 int end = lists.length - 1;
 while(end > 0){
 int start = 0;
 while (start < end){
 lists[start] = mergeTwoLists(lists[start], lists[end]);
 start ++;
 end --;
 }
 }

 return lists[0];
 }
Merge2X2: 把每一个listnode和前面merge的结果进行merge。TLE
public ListNode mergeKLists(ListNode[] lists) {
 if (lists == null || lists.length == 0) return null;
 while(l)
 ListNode cur = null;
 for (int i = 0; i < lists.length; i ++){
 cur = mergeTwoLists(cur, lists[i]); 
 }
 return cur;
 } 
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: