LeetCode LinkList 23. Merge k Sorted Lists

　　这两天一直也没有顾上记录一下自己做过的题目，回头看看，感觉忘的好快，今天做了一个hard,刚开始觉得挺难得，想了两种方法，一种是每次都从k个list中选取最小的一个，为空的直接跳过，再就是每次合并其中的两个list,直到最终合并完成，这就要用到地柜的方法，还有就是划分，感觉递归的思路比较清晰，就拿地柜的写了，使用递归的方法，这道题目就是以21. Merge Two Sorted Lists 为基础的。

　　阶梯思路就是，每次都从中间切割lists,直到切割完之后左侧或者右侧为，一个或者两个list就对其进行合并或者直接返回，合并的过程就是Merge Two Sorted Lists了，左右两侧都地柜完成之后，对他们返回的两个两遍进行合并。递归的程序看代码可能会比较好明白一点。

代码如下：

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; }

 * }

 */

class Solution {

    public ListNode mergeKLists(ListNode[] lists) {

        if(lists.length == )

            return null;

        return divide(lists,,lists.length-);

    }

    public ListNode divide(ListNode[] lists,int left,int right){

        if(left == right){

            return lists[left];

        }

        else if(left == right-){

            return merge2Lists(lists[left],lists[right]);

        }

        else{

            int mid = (left+right)/;

            ListNode leftNode = divide(lists,left,mid);

            ListNode rightNode = divide(lists,mid+,right);

            return merge2Lists(leftNode,rightNode);

        }

    }

    public ListNode merge2Lists(ListNode l1,ListNode l2){

        ListNode la = new ListNode(-),lm = la;

        while(l1!=null&&l2!=null){

            if(l1.val<l2.val){

                lm.next = l1;

                lm = l1;

                l1 = l1.next;

            }

            else{

                lm.next = l2;

                lm = l2;

                l2 = l2.next;

            }

        }

        lm.next = (l1!=null)?l1:l2;

        return la.next;

    }

}

小贴士：在合并两个链表的题目中，只要在最前面人为添加一个假的节点就可以避免好多关于头结点的判断，而最后只需要，将假节点跳过即可，在其他类型的链表题目中添加假节点，也不失为一种好方法。

巴特西

LeetCode LinkList 23. Merge k Sorted Lists

最新文章

热门文章