LeetCode題解之兩個(gè)有序鏈表合并

作者：積木zz 2021-01-28 08:20:41

開發(fā) 前端

關(guān)于空間復(fù)雜度，有可能有的朋友會(huì)覺得用到了m+n長度的鏈表?所以空間復(fù)雜度也是O(m+n)?

[[378893]]

前言

關(guān)于鏈表，常見的算法問題有以下幾種：

單鏈表反轉(zhuǎn)
兩個(gè)有序的鏈表合并
刪除鏈表倒數(shù)第n個(gè)結(jié)點(diǎn)
求鏈表的中間結(jié)點(diǎn)
鏈表中環(huán)的檢測

之前我們說過了第一個(gè)問題——單鏈表反轉(zhuǎn)，今天說說第二個(gè)問題：兩個(gè)有序的鏈表合并

題目：兩個(gè)有序的鏈表合并

輸入兩個(gè)遞增排序的鏈表，合并這兩個(gè)鏈表并使新鏈表中的節(jié)點(diǎn)仍然是遞增排序的。

示例1：

輸入：1->2->4, 1->3->4

輸出：1->1->2->3->4->4

限制：

0 <= 鏈表長度 <= 1000

解法一

先分析題干：遞增，鏈表，合并

兩個(gè)遞增的鏈表，合并成一個(gè)遞增的鏈表。

那么我們很容易想到一個(gè)方法就是，兩個(gè)指針分別遍歷兩個(gè)鏈表：

比如兩個(gè)鏈表是node1、node2，然后一個(gè)新鏈表node3作為輸出

node1.val< node2.val。那么就把node3指向node1，然后node1指針向下走一步，再和node2.val相比較。
node1.val> node2.val。那么就把node3指向node2，然后node2指針向下走一步，再和node1.val相比較。

什么時(shí)候結(jié)束呢?當(dāng)某個(gè)node.next為null的時(shí)候，就代表結(jié)束了。

比如node1遍歷結(jié)束，就把node3直接指向node2。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
 //創(chuàng)建要輸出的鏈表結(jié)點(diǎn)dum，和一個(gè)用于類指針操作的結(jié)點(diǎn)cur 
        ListNode dum = new ListNode(0); 
        ListNode cur = dum; 
        //結(jié)束條件是當(dāng)其中一個(gè)結(jié)點(diǎn)為空 
        while(l1 !=null && l2 != null){ 
         //當(dāng)鏈表1的結(jié)點(diǎn)小的時(shí)候，就把cur指向這個(gè)結(jié)點(diǎn)，并且鏈表1下移到下個(gè)結(jié)點(diǎn) 
            if(l1.val <= l2.val){ 
                cur.next=l1; 
                l1=l1.next; 
            }else { 
                cur.next=l2; 
                l2=l2.next; 
            } 
            cur=cur.next; 
        } 
        cur.next = (l1 == null? l2 : l1); 
        return dum.next; 
    }

時(shí)間復(fù)雜度

這個(gè)算法要遍歷兩個(gè)不同長度的鏈表，所以時(shí)間復(fù)雜度為O(m+n)

空間復(fù)雜度

關(guān)于空間復(fù)雜度，有可能有的朋友會(huì)覺得用到了m+n長度的鏈表?所以空間復(fù)雜度也是O(m+n)?

其實(shí)不然，鏈表并不會(huì)單獨(dú)創(chuàng)建額外的空間，我們其實(shí)只是新建了一個(gè)結(jié)點(diǎn)，然后將這個(gè)結(jié)點(diǎn)指向之前已經(jīng)有的結(jié)點(diǎn)空間地址，所以并沒有占用額外的m或者n大小的空間，只用到了dum和cur兩個(gè)結(jié)點(diǎn)的引用。

所以該解法的空間復(fù)雜度為O(1)

解法二

按照之前的格式，我們肯定會(huì)有第二種解法😄。

所以、我們需要想想，剛才的解法還有優(yōu)化點(diǎn)嗎?

是否可以不單獨(dú)創(chuàng)建鏈表結(jié)點(diǎn)呢?

其實(shí)可以發(fā)現(xiàn)我們每次操作都是類似的，都是比較大小，然后指定next結(jié)點(diǎn)。

所以我們可以寫成遞歸的寫法。

這里說下遞歸的兩個(gè)要素：

1、找到每一次遞歸過程中需要的操作。也就是我們剛才說的重復(fù)操作。

2、找到遞歸終止的條件。

那按照這個(gè)思路，我們就可以想想了：

首先，是每一次遞歸過程中需要做的操作，寫段偽代碼：

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

其次，我們要找到終止條件，也就是我們在解法一中類似的條件，當(dāng)某個(gè)鏈表便利結(jié)束，結(jié)點(diǎn)為空的時(shí)候。

if (l1 == null ) { 
 return l2; 
} 
if (l2 == null ) { 
 return l1; 
}

那么結(jié)合這兩個(gè)遞歸要素，我們就可以寫出一個(gè)遞歸解法：

public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
        if(l1 == null || l2 == null) 
            return l1 == null ? l2 : l1; 
 
        if(l1.val<l2.val) 
        { 
            l1.next = mergeTwoLists(l1.next, l2); 
            return l1; 
        } 
        else 
        { 
            l2.next = mergeTwoLists(l1, l2.next); 
            return l2; 
        } 
             
    }