023 Merge k Sorted Lists 合并K个有序链表

合并K个有序链表，并且作为一个有序链表的形式返回。分析并描述它的复杂度。

详见：https://leetcode.com/problems/merge-k-sorted-lists/description/

实现语言：Java

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

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

 * }

 */

class Solution {

    public ListNode mergeKLists(ListNode[] lists) {

        int n=lists.length;

        if(n==0){

            return null;

        }

        while(n>1){

            int k=(n+1)/2;

            for(int i=0;i<n/2;++i){

                lists[i]=mergeTwoLists(lists[i],lists[i+k]);

            }

            n=k;

        }

        return lists[0];

    }

    private ListNode mergeTwoLists(ListNode l1,ListNode l2){

        if(l1==null&&l2==null){

            return null;

        }

        if(l1==null){

            return l2;

        }

        if(l2==null){

            return l1;

        }

        ListNode head=new ListNode(-1);

        ListNode cur=head;

        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;

        }

        cur.next=l1!=null?l1:l2;

        return head.next;

    }

}

参考：https://www.cnblogs.com/grandyang/p/4606710.html

巴特西

023 Merge k Sorted Lists 合并K个有序链表

最新文章

热门文章