23题是一个综合性的题目,用前面做过的简单题目的累加就可以解出这一道题了,这道题最简单的办法是分治法,两两排序,最后再合并到一起,但是由于输入的是一个数组,所以此处不能用递归,21题可以作为它的子函数。
(分治法)
C# 代码
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { val = x; } * } */
public class Solution {
public ListNode MergeKLists(ListNode[] lists)
{
int Len = lists.Length;
if(Len ==0 ) return null;
ListNode MergedList =lists[0];
for(int i =1; i<Len; i++)
{
MergedList = MergeList(MergedList, lists[i]);
}
return MergedList;
}
public ListNode MergeList(ListNode headA,ListNode headB)
{
if(headA == null) return headB;
if(headB == null) return headA;
ListNode result = new ListNode(0);
ListNode Hc = result;
while(headA != null && headB != null)
{
if(headA.val > headB.val)
{
Hc.next = headB;
headB = headB.next;
}
else
{
Hc.next = headA;
headA = headA.next;
}
Hc = Hc.next;
}
if(headA != null){
headB = headA;
}
while(headB != null)
{
Hc.next = headB;
headB = headB.next;
Hc = Hc.next;
}
return result.next;
}
}