分析鏈表和遞歸問題

本篇內(nèi)容主要講解“分析鏈表和遞歸問題”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“分析鏈表和遞歸問題”吧!

企業(yè)建站必須是能夠以充分展現(xiàn)企業(yè)形象為主要目的，是企業(yè)文化與產(chǎn)品對外擴展宣傳的重要窗口，一個合格的網(wǎng)站不僅僅能為公司帶來巨大的互聯(lián)網(wǎng)上的收集和信息發(fā)布平臺，成都創(chuàng)新互聯(lián)公司面向各種領域：成都陽臺護欄等成都網(wǎng)站設計、營銷型網(wǎng)站解決方案、網(wǎng)站設計等建站排名服務。

鏈表與遞歸

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

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

原鏈表

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

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

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

更更短鏈表

更更更短鏈表

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

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

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

解題思路

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

反轉(zhuǎn)之前：

原鏈表

反轉(zhuǎn)之后：

新鏈表

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

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

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

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

「舉例」

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

示例

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

原鏈表尾節(jié)點

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

遞歸反轉(zhuǎn)

詳細步驟，如下動圖示：

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

Show me the Code

「C」

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

當然本題也可以采用「迭代」的方法去做，其代碼(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

「復雜度分析」

時間復雜度：「O(n)」，n 是鏈表的長度。對鏈表的每個節(jié)點都進行了反轉(zhuǎn)操作。

空間復雜度：「O(n)」，n 是鏈表的長度。遞歸調(diào)用的棧空間，最多為 n 層。

203. 移除鏈表元素

給你一個鏈表的頭節(jié)點 head 和一個整數(shù) val ，請你刪除鏈表中所有滿足   Node.val == val 的節(jié)點，并返回 新的頭節(jié)點 。  示例 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é)點，一般策略是「找到給點值的節(jié)點的前驅(qū)節(jié)點，然后讓其指向給定值的節(jié)點的后繼節(jié)點」。

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

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

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

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

「舉例」

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

示例動圖

Show me the Code

「C++」

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

「復雜度分析」

時間復雜度：「O(n)」，n 是鏈表的長度。遞歸需要遍歷鏈表一次。

空間復雜度：「O(n)」，n 是鏈表的長度。遞歸調(diào)用棧，最多不會超過 n 層。

到此，相信大家對“分析鏈表和遞歸問題”有了更深的了解，不妨來實際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學習！

網(wǎng)頁題目：分析鏈表和遞歸問題
網(wǎng)頁路徑：http://bm7419.com/article34/jjsdse.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、品牌網(wǎng)站制作、網(wǎng)站排名、定制網(wǎng)站、商城網(wǎng)站、企業(yè)網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)