每天一道算法題——合并兩個排序的連結清單

題目描述

輸入兩個單調遞增的連結清單，輸出兩個連結清單合成後的連結清單，當然我們需要合成後的連結清單滿足單調不減規則。

測試用例:

{1,3,5},{2,4,6}

對應輸出應該為:

{1,2,3,4,5,6}

分析：

1. >第一種方法采用建立一個連結清單nListNode來存儲合并排序後的表。在建立完之後将這個表的頭結點存儲下來，此處命名為head。并在合并操作完成後傳回頭結點即可（即return head.next；）
           

class ListNode {//連結清單的類定義
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Test1 {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if (list1==null) {
            return list2;
        } else if (list2==null) {
            return list1;
        }
        ListNode nListNode = new ListNode();
        nListNode.next = null;
        ListNode head = nListNode;
        while(list1!=null&&list2!=null){
            if (list1.val<list2.val) {
                nListNode.next = list1;
                nListNode = list1;
                list1 = list1.next;
            }else {
                nListNode.next = list2;
                nListNode = list2;
                list2 = list2.next;
            }
        }
         //把未結束的連結清單連接配接到合并後的連結清單尾部
        if (list1!=null) {
            nListNode.next = list1;
        }
        if (list2!=null) {
            nListNode.next  =list2;
        }
        return head.next;
    }
}
           

2. >另外一種方法就是利用遞歸的思想：
           

class ListNode {//連結清單的類定義
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Test1 {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if (list1==null) {
            return list2;
        } else if (list2==null) {
            return list1;
        }       
        while(list1!=null&&list2!=null){
            if (list1.val<list2.val) {
                list1.next = Merge(list1.next, list2);
                return list1;
            }else {
                list2.next = Merge(list1, list2.next);
                return list2;
            }
        }
        return null;
    }
}
           

運作測試：

第一種：

運作時間：19ms

占用記憶體：12512k

第二種：

運作時間：20ms

占用記憶體：12488k

總結：

從測試結果來看兩種方法的運算資源占用是差不多的。但是第一種算法更有益于加深對連結清單結構的了解，而且時間複雜度會更加的低，更加的适用于大規模的資料。