本篇內(nèi)容主要講解“分析鏈表和遞歸問題”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“分析鏈表和遞歸問題”吧!
企業(yè)建站必須是能夠以充分展現(xiàn)企業(yè)形象為主要目的，是企業(yè)文化與產(chǎn)品對外擴(kuò)展宣傳的重要窗口，一個(gè)合格的網(wǎng)站不僅僅能為公司帶來巨大的互聯(lián)網(wǎng)上的收集和信息發(fā)布平臺(tái)，成都創(chuàng)新互聯(lián)公司面向各種領(lǐng)域：成都陽臺(tái)護(hù)欄等成都網(wǎng)站設(shè)計(jì)、營銷型網(wǎng)站解決方案、網(wǎng)站設(shè)計(jì)等建站排名服務(wù)。
鏈表具有天然的遞歸性，一個(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ù)拆解，直到無法拆解
.jpg)
更更短鏈表
更更更短鏈表
有了這樣的思考，很多「鏈表」相關(guā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è)策略都可行，不過在面試中通常要求采用「策略2」。
由上面的「遞歸與鏈表」可知，本題也可以采用「遞歸法」去求解。
具體如何通過「遞歸」去解答呢?見下面例子。
「舉例」
鏈表 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)單鏈表
「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)雅，具體如下：
「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 是鏈表的長度。對鏈表的每個(gè)節(jié)點(diǎn)都進(jìn)行了反轉(zhuǎn)操作。
空間復(fù)雜度：「O(n)」，n 是鏈表的長度。遞歸調(diào)用的?？臻g，最多為 n 層。
給你一個(gè)鏈表的頭節(jié)點(diǎn) head 和一個(gè)整數(shù) val ，請你刪除鏈表中所有滿足 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)的過程，如下動(dòng)圖示。
示例動(dòng)圖
「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 是鏈表的長度。遞歸需要遍歷鏈表一次。
空間復(fù)雜度：「O(n)」，n 是鏈表的長度。遞歸調(diào)用棧，最多不會(huì)超過 n 層。
到此，相信大家對“分析鏈表和遞歸問題”有了更深的了解，不妨來實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！
