104.Merge k Sorted Lists-合并k个排序链表（中等题）

本文主要是介绍104.Merge k Sorted Lists-合并k个排序链表（中等题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

合并k个排序链表

1. 题目

   合并k个排序链表，并且返回合并后的排序链表。尝试分析和描述其复杂度。

2. 样例

   给出3个排序链表[2->4->null,null,-1->null]，返回 -1->2->4->null

3. 题解

先遍历删除空链表，再循环遍历头结点，最小值出列，直至只剩一条链表直接接入到排序链表尾部。

/*** Definition for ListNode.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int val) {*         this.val = val;*         this.next = null;*     }* }*/ 
public class Solution {/*** @param lists: a list of ListNode* @return: The head of one sorted list.*/public ListNode mergeKLists(List<ListNode> lists) {  ListNode dummy = new ListNode(1);ListNode head = dummy;for (int i=lists.size()-1;i>=0;i--){if (lists.get(i) == null){lists.remove(i);}}while (lists.size() > 1){ListNode min = lists.get(0);int index = 0;for (int i=lists.size()-1;i>=0;i--){if (lists.get(i).val < min.val){min = lists.get(i);index = i;}}lists.set(index,min.next);if (lists.get(index) == null){lists.remove(index);}head.next = min;head = head.next;}if (lists.size() == 1){head.next = lists.get(0);}return dummy.next;}
}

Last Update 2016.10.9

这篇关于104.Merge k Sorted Lists-合并k个排序链表（中等题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---