[leetcode 23]Merge k Sorted Lists

1 题目

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

2 思路

当时看到这个题目就想到的是归并排序。好吧，但是，具体代码写不出来。题目给的是数组：public ListNode mergeKLists(ListNode[] lists)，我就想，怎么归并排序，然后返回一个已经排好的，再进行递归。想破脑袋没想出来。

原来，可以赋值给一个ArrayList，然后，List还有一个牛逼的方法：lists.subLists(int i,int j)方法，前面的是包括，后面的是不包括，天然的用于分治策略啊。

看的别人代码链接：

https://leetcode.com/discuss/10012/a-solution-use-divide-and-conquer-algorithm-in-java

https://leetcode.com/discuss/9279/a-java-solution-based-on-priority-queue

3 代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) 
    {
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        ListNode head = new ListNode(0);
        ListNode node = head;
        
        ListNode list1 = l1;
        ListNode list2 = l2;
    
        while(list1 != null && list2 != null){
            if(list1.val > list2.val){
                node.next = list2;
                list2 = list2.next;
            }else{
                node.next = list1;
                list1 = list1.next;
            }
            node = node.next;
        }
        
        /* connect the longer list */
        if(list1 != null){
            node.next = list1;
        }
        if(list2 != null){
            node.next = list2;
        }
        
        return head.next;
    }

    public ListNode mergeKLists(List<ListNode> lists) {
        if(lists.size()==0) return null;
        if(lists.size()==1) return lists.get(0);
        if(lists.size()==2) return mergeTwoLists(lists.get(0),lists.get(1));
        
        ListNode node1 = mergeKLists(lists.subList(0,lists.size()/2));
        ListNode node2 = mergeKLists(lists.subList(lists.size()/2,lists.size()));
        
        return mergeTwoLists(node1,node2);
    }
    
    public ListNode mergeKLists(ListNode[] lists){
        List<ListNode> list = new ArrayList<>();
        for(ListNode node : lists){
            list.add(node);
        }
        return mergeKLists(list);
    }
    
}

看别人的代码，发现还有一个更简洁的递归写法：

return mergeTwoLists(mergeKLists(lists.subList(0, lists.size()/2)), mergeKLists(lists.subList(lists.size()/2, lists.size())));

感觉像是  调用一个递归，然后参数还是递归。屌爆了，希望将来能培养出这种思路和写法来。