[[403833]]

本文轉(zhuǎn)載自微信公眾號(hào)「程序員小熊」，作者程序員小熊。轉(zhuǎn)載本文請(qǐng)聯(lián)系程序員小熊公眾號(hào)。

前言

大家好，我是來(lái)自華為的「程序員小熊」。相信絕大部分童鞋都知道，在處理與「鏈表」相關(guān)問(wèn)題時(shí)，常用的解題套路主要包括「雙指針」、「迭代」和「虛擬頭節(jié)點(diǎn)」等等。

今天「小熊」主要介紹采用「遞歸」的策略，秒殺「鏈表」相關(guān)問(wèn)題，使得代碼更「優(yōu)雅」，并以兩道常見的面試題作為例題來(lái)講解，供大家參考，希望對(duì)大家有所幫助。

鏈表與遞歸

鏈表具有天然的遞歸性，一個(gè)鏈表可以看出頭節(jié)點(diǎn)后面掛接一個(gè)更短的鏈表，這個(gè)更短的鏈表是以原鏈表的頭節(jié)點(diǎn)的下一節(jié)點(diǎn)為頭節(jié)點(diǎn)，依次內(nèi)推，直到最后的更短的鏈表為空，空本身也是一個(gè)鏈表(最基礎(chǔ)的)。

以單鏈表 1->2->3->null 為例子，如下圖示：

原鏈表

將原鏈表看出頭節(jié)點(diǎn) 1 后掛接一個(gè)更短的鏈表

頭節(jié)點(diǎn)+更短鏈表

繼續(xù)拆解，直到無(wú)法拆解

更更短鏈表

更更更短鏈表

有了這樣的思考，很多「鏈表」相關(guān)問(wèn)題，都可以采用「遞歸」的思路來(lái)解答。

劍指 Offer 24. 反轉(zhuǎn)鏈表

定義一個(gè)函數(shù)，輸入一個(gè)鏈表的頭節(jié)點(diǎn)，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭節(jié)點(diǎn)。 
  
 
示例: 
 
輸入: 1->2->3->4->5->NULL 
輸出: 5->4->3->2->1->NULL 
  
 
限制： 
0 <= 節(jié)點(diǎn)個(gè)數(shù) <= 5000 

解題思路

要反轉(zhuǎn)鏈表，即將原鏈表的頭節(jié)點(diǎn)變?yōu)樾骆湵淼奈补?jié)點(diǎn)，原鏈表的尾節(jié)點(diǎn)變?yōu)樾骆湵淼念^節(jié)點(diǎn)。如下圖示：

反轉(zhuǎn)之前：

原鏈表

反轉(zhuǎn)之后：

新鏈表

主要策略主要有：1、直接修改鏈表的值，如上圖中的原鏈表圖所示，將原鏈表值 1 的頭節(jié)點(diǎn)改為原鏈表尾節(jié)點(diǎn)的值，依次類推;2、讓遍歷整個(gè)鏈表，讓鏈表的尾節(jié)點(diǎn)指向其前一個(gè)節(jié)點(diǎn)，依次類推。

雖然這兩個(gè)策略都可行，不過(guò)在面試中通常要求采用「策略2」。

由上面的「遞歸與鏈表」可知，本題也可以采用「遞歸法」去求解。

具體如何通過(guò)「遞歸」去解答呢?見下面例子。

「舉例」

鏈表 1->2->3->null 為例子，如下圖示。

示例

不斷遍歷找到原鏈表為尾節(jié)點(diǎn)，即新鏈表的頭節(jié)點(diǎn)。

原鏈表尾節(jié)點(diǎn)

然后讓尾節(jié)點(diǎn)指向其前驅(qū)節(jié)點(diǎn)，依次類推。

遞歸反轉(zhuǎn)

詳細(xì)步驟，如下動(dòng)圖示：

遞歸反轉(zhuǎn)單鏈表

Show me the Code

「C」

struct ListNode* reverseList(struct ListNode* head){ 
    /* 遞歸終止條件 */ 
    if (head == NULL || head->next == NULL) { 
        return head; 
    } 
 
    /* 反轉(zhuǎn)當(dāng)前所在的鏈表節(jié)點(diǎn) */ 
    struct ListNode* newHead = reverseList(head->next); 
 
    /* 由原鏈表的尾節(jié)點(diǎn)挨個(gè)指向其前驅(qū)節(jié)點(diǎn) */ 
    head->next->next = head; 
 
    /* 防止成環(huán) */ 
    head->next = NULL; 
 
    /* 返回新的鏈表頭節(jié)點(diǎn) */ 
    return newHead; 
} 

「java」

ListNode reverseList(ListNode head) { 
    if (head == null || head.next == null) { 
        return head; 
    } 
 
    ListNode node = reverseList(head.next); 
    head.next.next = head; 
    head.next = null; 
 
    return node; 
} 

當(dāng)然本題也可以采用「迭代」的方法去做，其代碼(python 版)也很優(yōu)雅，具體如下：

Show me the Code

「python」

def reverseList(self, head: ListNode) -> ListNode: 
    cur, pre = head, None 
    while cur: 
        cur.next, pre, cur = pre, cur, cur.next 
         
    return pre  

「復(fù)雜度分析」

時(shí)間復(fù)雜度：「O(n)」，n 是鏈表的長(zhǎng)度。對(duì)鏈表的每個(gè)節(jié)點(diǎn)都進(jìn)行了反轉(zhuǎn)操作。

空間復(fù)雜度：「O(n)」，n 是鏈表的長(zhǎng)度。遞歸調(diào)用的?？臻g，最多為 n 層。

203. 移除鏈表元素

給你一個(gè)鏈表的頭節(jié)點(diǎn) head 和一個(gè)整數(shù) val ，請(qǐng)你刪除鏈表中所有滿足  
 
Node.val == val 的節(jié)點(diǎn)，并返回 新的頭節(jié)點(diǎn) 。 
 
示例 1： 
 
輸入：head = [1,2,6,3,4,5,6], val = 6 
輸出：[1,2,3,4,5] 
 
示例 2： 
 
輸入：head = [], val = 1 
輸出：[] 
 
示例 3： 
 
輸入：head = [7,7,7,7], val = 7 
輸出：[] 

解題思路

要移除鏈表中給定值的節(jié)點(diǎn)，一般策略是「找到給點(diǎn)值的節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，然后讓其指向給定值的節(jié)點(diǎn)的后繼節(jié)點(diǎn)」。

例如要?jiǎng)h除鏈表 1->2->3->null 中，節(jié)點(diǎn)值為 3 的節(jié)點(diǎn)，就得先找到其前驅(qū)節(jié)點(diǎn)(值為 2 的節(jié)點(diǎn))，如下圖示：

刪除給定值的節(jié)點(diǎn)

由上面的「遞歸與鏈表」可知，本題同樣也可以采用「遞歸法」去求解，不斷刪除更短鏈表中給定值的節(jié)點(diǎn)，然后再將處理后的更短的鏈表，掛接在其前驅(qū)節(jié)點(diǎn)后。

「注意」最后要判斷原鏈表的頭節(jié)點(diǎn)是否是待移除的節(jié)點(diǎn)。

「舉例」

以鏈表 1->2->3->null 為例子，移除鏈表中給定值的節(jié)點(diǎn)的過(guò)程，如下動(dòng)圖示。

示例動(dòng)圖

Show me the Code

「C++」

ListNode* removeElements(ListNode* head, int val) { 
    /* 遞歸終止條件 */ 
    if(head == NULL) { 
        return NULL; 
    } 
 
    /* 刪除鏈表中頭節(jié)點(diǎn)后值為 val 的元素的節(jié)點(diǎn) */ 
    head->next=removeElements(head->next,val); 
 
    /* 判斷頭節(jié)點(diǎn)是否為值為 val 的節(jié)點(diǎn)，再返回*/ 
    return head->val==val ? head->next : head; 
} 

「Golang」

func removeElements(head *ListNode, val int) *ListNode { 
    if head == nil { 
        return head 
    } 
 
    head.Next = removeElements(head.Next, val) 
    if head.Val == val { 
        return head.Next 
    } 
 
    return head 
} 

「復(fù)雜度分析」

時(shí)間復(fù)雜度：「O(n)」，n 是鏈表的長(zhǎng)度。遞歸需要遍歷鏈表一次。

空間復(fù)雜度：「O(n)」，n 是鏈表的長(zhǎng)度。遞歸調(diào)用棧，最多不會(huì)超過(guò) n 層。