Leetcode系列之链表（13）

题目：

合并k个已排序的链表并将其作为一个已排序的链表返回。分析并描述其复杂度。

思路：

典型的多路归并问题

代码：

import java.util.*;

/**

* Definition for singly-linked list.

* public class ListNode {

*    int val;

*    ListNode next;

*    ListNode(int x) {

*        val = x;

*        next = null;

*    }

* }

*/

public class Solution {

    public ListNode mergeKLists(ArrayList<ListNode> lists) {

        if (lists == null || lists.size() == 0) {

            return null;

        }

        while(lists.size() > 1) {

            ArrayList<ListNode> newLists = new ArrayList<ListNode>();

            for(int i=0;i+1<lists.size();i=i+2) {

                ListNode mergedList = mergeTwoLists(lists.get(i), lists.get(i+1));

                newLists.add(mergedList);

            }

            if(lists.size()%2 == 1) {

                newLists.add(lists.get(lists.size()-1));

            }

            lists = newLists;

        }

        return lists.get(0);

    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode head = new ListNode(0);

        ListNode point = head;

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

            if(l1.val<l2.val) {

                point.next = l1;

                l1 = l1.next;

            }

            else {

                point.next = l2;

                l2 = l2.next;

            }

            point = point.next;

        }

        if(l1!=null) {

            point.next = l1;

        }

        if(l2!=null) {

            point.next = l2;

        }

        return head.next; 

    }

}