LeetCode--合并兩個(gè)有序鏈表-創(chuàng)新互聯(lián)

10年積累的成都網(wǎng)站制作、網(wǎng)站設(shè)計(jì)經(jīng)驗(yàn)，可以快速應(yīng)對(duì)客戶對(duì)網(wǎng)站的新想法和需求。提供各種問(wèn)題對(duì)應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先網(wǎng)站制作后付款的網(wǎng)站建設(shè)流程，更有萊西免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

方法一：遞歸解決

對(duì)于此題自然不用多說(shuō)，既然合并后也是有序鏈表，則是將兩個(gè)鏈表的值依次比較，隨后插入新鏈表中即可。老生常談，我們先對(duì)兩個(gè)鏈表是否為空進(jìn)行判斷，若為空，則返回另一個(gè)鏈表。若不為空，我們則需要重新去討論。

不為空的情況下，

1、若list1中的值小于list2的值時(shí)，我們將list1的頭結(jié)點(diǎn)放入新鏈表中，然后遞歸調(diào)用將list1中第二個(gè)值再與list2進(jìn)行比較，進(jìn)行遞歸

2、list2中的值小于list1的值時(shí)同理。

3、最后返回新鏈表newHead。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* newHead;
        if(list1==nullptr)
            return list2;
        else if(list2==nullptr)
            return list1;
        else{
            if(list1->valval){
                newHead=list1;
                newHead->next=mergeTwoLists(list1->next,list2);
            }
            else{
               newHead=list2;
                newHead->next=mergeTwoLists(list2->next,list1);
            }
        }
        return newHead; 
    }
};

但我們可以明顯看出來(lái)，遞歸使用的時(shí)間復(fù)雜度和空間復(fù)雜度都是較高的，因?yàn)檫f歸需要使用函數(shù)棧進(jìn)行操作，所以會(huì)導(dǎo)致復(fù)雜度較高。

復(fù)雜度分析：

時(shí)間復(fù)雜度為O(m+n)，因?yàn)楸闅v了兩個(gè)鏈表。

空間復(fù)雜度為O(m+n)，因?yàn)樾枰骆湵韥?lái)進(jìn)行存儲(chǔ)，長(zhǎng)度為m+n。

m,n為兩個(gè)鏈表的長(zhǎng)度。

方法二：迭代

這個(gè)解法是根據(jù)LeetCode的題解來(lái)實(shí)現(xiàn)的，下面一張解析的圖片也是截取LeetCode官方題解。

此處的哨兵節(jié)點(diǎn)我依稀記得在數(shù)據(jù)結(jié)構(gòu)與算法這門(mén)課學(xué)過(guò)，但已經(jīng)忘記，這個(gè)知識(shí)點(diǎn)需要掌握。

代碼如下：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* preHead = new ListNode(0);

        ListNode* prev = preHead;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val< l2->val) {
                prev->next = l1;
                l1 = l1->next;
            } else {
                prev->next = l2;
                l2 = l2->next;
            }
            prev = prev->next;
        }

        // 合并后 l1 和 l2 最多只有一個(gè)還未被合并完，我們直接將鏈表末尾指向未合并完的鏈表即可
        prev->next = l1 == nullptr ? l2 : l1;

        return preHead->next;

    }
};

var mergeTwoLists = function(list1, list2) {
    let head = new ListNode(null,null);
    let temp = head;

    while(l1 != null && l2 != null) {

        if(l1.val<= l2.val) {
            temp.next = l1;
            temp = l1;
            l1 = l1.next;
        }else {
            temp.next = l2;
            temp = l2;
            l2 = l2.next;
        }
    }

    if(l1 != null) {
        temp.next = l1; 
    }

    if(l2 != null) {
        temp.next = l2;
    }

    return head.next;
};

js的代碼也是大同小異，思路是一樣的。

復(fù)雜度分析：

時(shí)間復(fù)雜度為O(m+n)，還是遍歷兩個(gè)鏈表。

空間復(fù)雜度為O(1)。因?yàn)槊看未鎯?chǔ)的數(shù)據(jù)用常數(shù)級(jí)就行。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁(yè)名稱：LeetCode--合并兩個(gè)有序鏈表-創(chuàng)新互聯(lián)
文章URL：http://m.jiaotiyi.com/article/dgcgcs.html