前言
大家好，我是來自「華為」的「程式員小熊」，絕大部分童鞋都知道，解決「鏈表」相關問題時，常用的解題套路主要包括「雙指標」、「迭代」和「虛擬頭節點」等等，
今天「小熊」介紹采用「遞回」的策略，秒殺「鏈表」相關問題，使得代碼更「優雅」，并以兩道常見的面試題作為例題來講解，供大家參考，希望對大家有所幫助，
鏈表與遞回
鏈表具有天然的遞回性，一個鏈表可以看出頭節點后掛接一個更短的鏈表，這個更短的鏈表是以原鏈表的頭節點的下一節點為頭節點，依次內推，直到最后的更短的鏈表為空，空本身也是一個鏈表（最基礎的），
以單鏈表 1->2->3->null 為例子，如下圖示：
將原鏈表看出頭節點 1 后掛接一個更短的鏈表
繼續拆解，直到無法拆解
有了這樣的思考，很多「鏈表」相關問題，都可以采用「遞回」的思路來解答，
劍指 Offer 24. 反轉鏈表
解題思路
要反轉鏈表，即將原鏈表的頭節點變為新鏈表的尾節點，原鏈表的尾節點變為新鏈表的頭節點，如下圖示：
反轉之前：
反轉之后：
主要策略主要有：1、修改鏈表的值，如上圖示，將原鏈表頭節點的值 1 改為原鏈表尾節點的值 3，依次類推；2、讓遍歷整個鏈表，讓鏈表的尾節點指向其前一個節點，依次類推，
雖然這兩個策略都可行，不過在面試中通常要求采用「策略2」，
由上面的「遞回與鏈表」可知，本題也可以采用「遞回法」去求解，
具體如何通過「遞回」去解答呢？見下面例子，
「舉例」
鏈表 1->2->3->null 為例子，如下圖示，
不斷遍歷找到原鏈表為尾節點，即新鏈表的頭節點，
然后讓尾節點指向其前驅節點，依次類推，
詳細步驟，如下動圖示：
Show me the Code
1 // c 語言 2 struct ListNode* reverseList(struct ListNode* head){ 3 /* 遞回終止條件 */ 4 if (head == NULL || head->next == NULL) { 5 return head; 6 } 7 8 /* 反轉當前所在的鏈表節點 */ 9 struct ListNode* newHead = reverseList(head->next); 10 11 /* 由原鏈表的尾節點挨個指向其前驅節點 */ 12 head->next->next = head; 13 14 /* 防止成環 */ 15 head->next = NULL; 16 17 /* 回傳新的鏈表頭節點 */ 18 return newHead; 19 }View Code
1 // Java 2 ListNode reverseList(ListNode head) { 3 if (head == null || head.next == null) { 4 return head; 5 } 6 7 ListNode node = reverseList(head.next); 8 head.next.next = head; 9 head.next = null; 10 11 return node; 12 }View Code
當然本題也可以采用「迭代」的方法去做，其代碼（python 版）也很優雅，具體如下：
Show me the Code
1 # Python3 2 def reverseList(self, head: ListNode) -> ListNode: 3 cur, pre = head, None 4 while cur: 5 cur.next, pre, cur = pre, cur, cur.next 6 7 return preView Code
「復雜度分析」
時間復雜度：「O(n)」，其中 n 是鏈表的長度，對鏈表的每個節點都進行了反轉操作，
空間復雜度：「O(n)」，其中 n 是鏈表的長度，遞回呼叫的堆疊空間，最多為 n 層，
203. 移除鏈表元素
解題思路
要移除鏈表中給定值的節點，一般策略是「找到給點值的節點的前驅節點，然后讓其指向給定值的節點的后繼節點」，
例如要洗掉鏈表 1->2->3->null 中，節點值為 3 的節點，就得先找到其前驅節點（值為 2 的節點），如下圖示：
由上面的「遞回與鏈表」可知，本題同樣也可以采用「遞回法」去求解，不斷洗掉更短鏈表中給定值的節點，然后再將處理后的更短的鏈表，掛接在其前驅節點后，
「注意」
最后要判斷原鏈表的頭節點是否是待移除的節點，
「舉例」
以鏈表 1->2->3->null 為例子，移除鏈表中給定值的節點的程序，如下動圖示，
Show me the Code
1 // C++ 2 ListNode* removeElements(ListNode* head, int val) { 3 /* 遞回終止條件 */ 4 if(head == NULL) { 5 return NULL; 6 } 7 8 /* 洗掉鏈表中頭節點后值為 val 的元素的節點 */ 9 head->next=removeElements(head->next,val); 10 11 /* 判斷頭節點是否為值為 val 的節點，再回傳*/ 12 return head->val==val ? head->next : head; 13 }View Code
1 // Golang 2 func removeElements(head *ListNode, val int) *ListNode { 3 if head == nil { 4 return head 5 } 6 7 head.Next = removeElements(head.Next, val) 8 if head.Val == val { 9 return head.Next 10 } 11 12 return head 13 }View Code
「復雜度分析」
時間復雜度：「O(n)」，其中 n 是鏈表的長度，遞回需要遍歷鏈表一次，
空間復雜度：「O(n)」，其中 n 是鏈表的長度，遞回呼叫堆疊，最多不會超過 n 層，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/285768.html
標籤：其他