# LeetCode 23：Merge k Sorted Lists

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

Example:

```Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6```

Java源码

`package com.maoxiaomeng;import java.util.ArrayList;import java.util.Collections;import java.util.List;/** * Copyright (C), 2014-2018, maoxiaomeng.com * FileName: Solution * Author:   lihui * Date:     2018/4/14 00:37 */class ListNode {    int val;    ListNode next;    ListNode(int x) {        val = x;    }}public class Solution {    public ListNode mergeKLists(ListNode[] lists) {        if (lists.length == 0) {            return null;        }        List<Integer> myList = new ArrayList<Integer>();        for (ListNode list : lists) {            while (list != null) {                myList.add(list.val);                list = list.next;            }        }        Collections.sort(myList);        ListNode l = new ListNode(myList.get(0));        ListNode head = l;        int i = 1;        while (i < myList.size()) {            l.next = new ListNode(myList.get(i));            l = l.next;            i++;        }        return head;    }}`

`package com.maoxiaomeng;/** * Copyright (C), 2014-2018, maoxiaomeng.com * FileName: Solution * Author:   lihui * Date:     2018/4/14 00:37 */class ListNode {    int val;    ListNode next;    ListNode(int x) {        val = x;    }}public class Solution {    public ListNode mergeKLists(ListNode[] lists) {        int len = lists.length;        if (lists == null || len == 0) {            return null;        }  else if (len == 1) {            return lists[0];        }            while (len > 1) {            int middle = (len + 1) / 2;            for (int i = 0; i < len / 2; i++) {                lists[i] = merge(lists[i], lists[i + middle]);            }            len = middle;        }        return lists[0];    }        public  ListNode merge(ListNode left, ListNode right) {        if (left == null) {            return right;        }        if (right == null) {            return left;        }        ListNode head = new ListNode(0);        ListNode current = head;        while (left != null && right != null) {            if (left.val < right.val) {                current.next = left;                left = left.next;            } else {                current.next = right;                right = right.next;            }            current = current.next;        }        if (left != null) {            current.next = left;        } else {            current.next = right;        }        return head.next;    }}`