分治法解決 n個連結清單合并的問題

問題回顧：兩個單連結清單合并

代碼如下：

定義單連結清單：

class ListNode {

int val;

ListNode next;

ListNode(int x) {

val = x;

}

}

采用遞歸的方式合并，主要要判斷是否為空

public class Solution {

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

if(l1==null)

return l2;

if(l2==null)

return l1;///先判斷是否為空  

ListNode listnode;

if(l1.val<l2.val)

{

listnode=l1;

listnode.next=mergeTwoLists(l1.next,l2);

}

else

{

listnode=l2;

listnode.next=mergeTwoLists(l1,l2.next);

}

return listnode;

   }

public static void main(String[] args) {

// TODO Auto-generated method stub

}

}

現在題目要求：合并n個單連結清單，則采用“分治政策”

代碼如下：

class ListNode {// Java連結清單結構

int val;

ListNode next;

ListNode(int x) {

val = x;

}

}

public class Solution {

public ListNode mergeKLists(ListNode[] lists) {

return mergeklist(lists, 0, lists.length - 1);

}

public static ListNode mergeklist(ListNode[] lists, int start, int end) {

if (start == end)

return lists[start];

if (start < end) {

int temp = (start + end) / 2;

ListNode l1 = mergeklist(lists, start, temp);

ListNode l2 = mergeklist(lists, temp + 1, end);

return merge(l1, l2);

} else

return null;

}

public static ListNode merge(ListNode l1, ListNode l2)// 采用遞歸的方式拼接兩個連結清單

{

if (l1 == null)

return l2;

if (l2 == null)

return l1;

if (l1.val < l2.val) {

l1.next = merge(l1.next, l2);

return l1;

} else {

l2.next = merge(l1, l2.next);

return l2;

}

}

public static void main(String[] args) {

// TODO Auto-generated method stub

}

}