多路歸并排序練習

BM5 合并k個已排序的連結清單

題目描述

合并 k 個升序的連結清單并将結果作為一個升序的連結清單傳回其頭節點。

資料範圍：節點總數滿足 0 \le n \le 10^50≤n≤10

連結清單個數滿足 1 \le k \le 10^5 \1≤k≤10 ，每個連結清單的長度滿足 1 \le len \le 200 \1≤len≤200 ，每個節點的值滿足 |val| <= 1000∣val∣<=1000

要求：時間複雜度 O(nlogk)O(nlogk)

最近一邊忙着進行忙着複習準備軟考一邊開始刷牛客網，最初看到這題的時候第一反應就是進行歸并排序

歸并排序屬于穩定排序，時間複雜度為O(nlogn)，且在最壞情況下的時間複雜度仍為O(nlogn)。

詳細代碼

import java.util.*;
//結點ListNode的資料結構
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;
        }
        
    	return mergeSort(lists, 0, lists.size()-1);
        
        
    }
    
    //歸并排序采用分治法，以遞歸形式實作二路歸并排序
    public ListNode mergeSort(List<ListNode> lists, int left, int right){
        int mid;
        if(left<right){
            mid = (left+right)/2;
            
            //node1,node2得到兩條前後相鄰的有序鍊
            ListNode node1 = mergeSort(lists, left, mid);
            ListNode node2 = mergeSort(lists, mid+1, right);
            return mergeTwoList(node1, node2);
        }
        return lists.get(left);
    } 
    
    //二路歸并排序
    public ListNode mergeTwoList(ListNode node1, ListNode node2){    
        ListNode new_list_node = new ListNode(Integer.MAX_VALUE);//新連結清單的頭結點不存儲有效資料
        ListNode tmp_new = new_list_node;//設定遊标
        
        while(node1!=null && node2!=null){
            if(node1.val<=node2.val){//使用小于等于号<=，確定排序穩定
                tmp_new.next = node1;
                node1 = node1.next;
            }else{
                tmp_new.next = node2;
                node2 = node2.next;
            }
            tmp_new = tmp_new.next;
        }
        
        //将餘下的元素全部按順序接入合并有序鍊的尾部
        while(node1!=null){
            tmp_new.next = node1;
            node1 = node1.next;
            tmp_new = tmp_new.next;
        }
        
        while(node2!=null){
            tmp_new.next = node2;
            node2 = node2.next;
            tmp_new = tmp_new.next;
        }
        
        return new_list_node.next;//傳回新連結清單的第一個有效結點
    }
 }
           

代碼性能

性能确實有點捉急啊

參考資料

[1]:《軟體設計師教程 第五版》(清華大學出版社) P173