目錄
- 鏈表中的遞回性質
- 前言
- LeetCode 上關于鏈表的一道問題
- 203 號題目 移除鏈表中的元素
- 遞回的基本概念與示例
- 鏈表天然的遞回性
- 小結
鏈表中的遞回性質
前言
在前面的 鏈表的資料結構的實作 中，已經對鏈表資料結構的實作程序有了充分的了解了，但是對于鏈表而言，其實它還和遞回相關聯，雖然一般來說遞回在樹的資料結構中使用較多，因為在樹這個結構中使用遞回是非常方便的，在鏈表這個資料結構中也是可以使用遞回的，因為鏈表本身具有天然的遞回性質，只不過鏈表是一種線性結構，通常使用非遞回的方式也可以很容易地實作它，所以大多數情況下都是使用回圈的方式來實作鏈表，不過如果在鏈表中使用遞回，可以幫助打好遞回的基礎以在后面可以更加深入地理解樹這種資料結構和一些遞回演算法，這是非常具有好處的，所以在這里可以借助 LeetCode 上的一道關于鏈表的問題，使用遞回的方式去解決它，以此達到理解鏈表中的遞回性質的目的，
LeetCode 上關于鏈表的一道問題
203 號題目 移除鏈表中的元素
題目描述:
洗掉鏈表中等于給定值 val 的所有節點，
示例:
輸入: 1->2->6->3->4->5->6, val = 6
輸出: 1->2->3->4->5
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/remove-linked-list-elements
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
題目提供的鏈表結點類:
/**
* Definition for singly-linked list.
*/
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
題目提供的解題模板:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
}
}
-對于此題，可以先嘗試使用非遞回的方式然后使用虛擬頭節點和不使用虛擬頭節點分別實作來回顧一下鏈表的洗掉邏輯，
非遞回方式及不使用虛擬頭節點題解思路:
-
如果不使用虛擬頭結點，那么首先可以直接判斷 head 是否不為 null 以及它的值是否是要洗掉的元素，如果是則洗掉當前頭節點，此處需要注意的是，很可能會存在多個要洗掉的元素都堆在鏈表頭部或者整個鏈表都是要洗掉的元素，所以這里可以使用 while 回圈來判斷依次洗掉鏈表的當前頭節點，
-
處理完頭部部分后，就處理中間部分需要洗掉的元素，此時回顧一下鏈表的洗掉邏輯，需要先找到待洗掉節點的前置節點，所以以鏈表此時的頭節點 head 開始，將其作為第一個前置節點 prev（因為此時頭部已經處理完畢，沒有要洗掉的元素了），再通過 while 回圈依次判斷 prev 的下一個節點是否需要洗掉直到洗掉完所有要洗掉的元素為止，
-
最后回傳頭節點 head 即可，此時通過 head 可以獲得洗掉元素后的鏈表，
以上思路實作為代碼如下：
public class Solution {
public ListNode removeElements(ListNode head, int val) {
// 非遞回不使用虛擬頭結點的解決方案
// 把鏈表開始部分需要洗掉的元素洗掉
while (head != null && head.val == val) {
ListNode delNode = head;
head = head.next;
delNode.next = null;
}
// 如果此時 head == null,說明鏈表中所有元素都需要洗掉,此時回傳 head 或 null
if (head == null) {
return null;
}
// 處理鏈表中間需要洗掉的元素
ListNode prev = head;
// 每次看 prev 的下一個元素是否需要被洗掉
while (prev.next != null) {
if (prev.next.val == val) {
ListNode delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
} else {
prev = prev.next;
}
}
return head;
}
}
提交結果:
接下來就使用虛擬頭結點的方式來實作此題，思路如下：
-
創建一個虛擬頭節點，并指向鏈表的頭節點 head，
-
此時整個鏈表的所有元素都有一個前置節點，就可以統一使用通過前置節點的方式來洗掉待洗掉元素，此時以虛擬頭節點開始，將其作為第一個前置節點 prev，再通過 while 回圈依次判斷 prev 的下一個節點是否需要洗掉直到洗掉完所有要洗掉的元素為止，
-
最后回傳虛擬頭節點的下一個節點即可，即回傳 head，
以上思路實作為代碼如下:
public class Solution {
public ListNode removeElements(ListNode head, int val) {
// 非遞回使用虛擬頭結點的解決方案
// 創建虛擬頭節點
ListNode dummyHead = new ListNode(-999);
dummyHead.next = head;
// 處理鏈表中需要洗掉的元素
ListNode prev = dummyHead;
// 每次看 prev 的下一個元素是否需要被洗掉
while (prev.next != null) {
if (prev.next.val == val) {
ListNode delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
} else {
prev = prev.next;
}
}
// 回傳鏈表頭節點
return dummyHead.next;
}
}
提交結果:
此時，兩種方案都正確的運行了，對于鏈表的洗掉邏輯在使用虛擬頭節點和不使用虛擬頭節點的情況都實作了一遍，這也是在之前的鏈表的資料結構的實作中涉及到的部分，這里再次回顧一遍加深印象，也方便后面使用遞回方式實作該題目后對比兩種不同方式的異同，
遞回的基本概念與示例
對于遞回，本質上，就是將原來的問題，轉化為更小的同一問題，直到轉化為基本問題并解決基本問題后，再一步步的將結果回傳達到求解原問題的目的，
舉個例子：陣列求和，
從圖中可以看出，其實遞回也就是將原問題的規模一步步地縮小，一直縮小到基本問題出現然后解出基本問題的解再往上依次回傳根據這個基本解依次求出各個規模的解直到求出原問題的解，
以上程序編碼實作如下：
/**
* 陣列求和遞回示例
*
* @author 踏雪彡尋梅
* @date 2020/2/8 - 10:30
*/
public class Sum {
/**
* 對 array 求和
*
* @param array 求和的陣列
* @return 回傳求和結果
*/
public static int sum(int[] array) {
// 計算 array[0...n) 區間內所有數字的和
return sum(array, 0);
}
/**
* 計算 array[l...n) 這個區間內所有數字的和
*
* @param array 求和的陣列
* @param l 左邊界
* @return 回傳求和的結果
*/
private static int sum(int[] array, int l) {
// 基本問題: 陣列為空時回傳 0
if (l == array.length) {
return 0;
}
// 把原問題轉換為小問題解決
return array[l] + sum(array, l + 1);
}
/**
* 測驗陣列求和
*/
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5, 6, 7, 8};
System.out.println(sum(nums));
}
}
運行結果:
對于以上例子，可以這樣理解：在使用遞回時，可以注意遞回函式的“宏觀”語意，在上面的例子中，“宏觀”語意就是計算 array[l...n) 區間內所有數字的和，這樣子理解遞回函式再去觀看函式中的將原問題轉換成小問題時，會更好地理解這個函式要做的事情，簡單來說遞回函式就是一個完成一個功能的函式，只不過是自己呼叫自己，每一次轉換成小問題時完成的功能都是陣列的某個數加上剩余數的和，直到無數可加為止，這個陣列求和的遞回程序如下圖所示：
也可以使用下圖表示，下圖中的代碼是進行拆分后的代碼，為了更方便地展示程序：
至此，已經大致了解了遞回的基本概念和基本流程了，接下來就看看鏈表所具有的天然的遞回性質，
鏈表天然的遞回性
對于鏈表而言，本質上就是將一個個節點掛接起來組成的，也就是下圖的這個樣子：
而其實對于鏈表，也可以應用遞回理解成是由一個頭節點后面掛接著一個更短的鏈表組成的，也就是下圖的這個樣子：
對于上圖中的一個更短的鏈表，其中也是由一個頭節點掛接著一個更短的鏈表形成的，依次類推，直到最后為 NULL 時，NULL 其實也就是一個鏈表了，此時就是遞回方式的鏈表的基本問題，
所以此時再看回之前的 203 號題目：移除鏈表中的元素，就可以將題目提供的鏈表看成上圖所示的結構，然后使用遞回解決更小的鏈表中要洗掉的元素得到這個小問題的解，之后再看頭節點是否需要洗掉，如果要洗掉就回傳小問題的解，此時也就是原問題的解了；不洗掉的話就將頭節點和小問題的解組合起來回傳回去得到原問題的解，這個程序用圖來表示為以下圖示：
用代碼實作后如下所示：
public class Solution {
public ListNode removeElements(ListNode head, int val) {
// 使用遞回解決鏈表中移除元素
// 構建基本問題,鏈表為空時回傳 null
if (head == null) {
return null;
}
// 構建小問題: 得到頭節點后掛接著的更小的鏈表的解
ListNode result = removeElements(head.next, val);
// 判斷頭節點是否需要洗掉,和小問題的解組合得到原問題的解
if (head.val == val) {
// 頭節點需要洗掉
return result;
} else {
// 頭節點不需要洗掉,和小問題的解組合得到原問題的解
head.next = result;
return head;
}
}
}
提交結果:
從提交結果可以驗證實作的邏輯是沒有錯誤的，此時代碼還可以進行簡化如下：
public class Solution {
public ListNode removeElements(ListNode head, int val) {
// 使用遞回解決鏈表中移除元素
// 構建基本問題,鏈表為空時回傳 null
if (head == null) {
return null;
}
// 構建小問題: 得到頭節點后掛接著的更小的鏈表的解,然后掛接在頭節點后面
head.next = removeElements(head.next, val);
// 判斷頭節點是否需要洗掉,和小問題的解組合得到原問題的解
return head.val == val ? head.next : head;
}
}
提交結果:
此時對比前面的非遞回方式實作的題解，可以發現使用遞回方式實作是非常優雅的，代碼十分簡潔易讀，接下來就分析一下該遞回運行的機制，遞回運行程序如下圖所示：
至此，這個題目的遞回流程就走完了，對于以上程序，就是子程序的一步步呼叫，呼叫完畢之后，子程序計算出結果，再一步步地回傳結果給上層呼叫，最終得到了結果，節點的洗掉發生在第 6 行陳述句上，這行陳述句也就是解決了更小規模的問題后得到解后組織當前呼叫構成了當前問題的解，
與此同時，需要注意的是遞回呼叫是有代價的，代價則是函式的呼叫和使用系統堆疊空間這兩方面，在函式呼叫時是需要一些時間開銷的，其中包括需要記錄當前函式執行到哪個位置、函式中的區域變數是處于怎樣的等等，然后將這個狀態給壓入系統堆疊，然后在遞回呼叫的程序中，是需要消耗系統堆疊的空間的，所以對于遞回函式，如果不處理基本問題的話，遞回函式將一直執行下去，直到將系統堆疊的空間使用完，同時如果使用遞回處理資料量巨大的情況的時候，也有可能會使用完系統堆疊空間，比如上面的陣列求和如果求和百萬級別、千萬級別的資料系統堆疊空間是不夠用的，在鏈表中洗掉元素也是如此，如果鏈表過長系統堆疊空間也是不夠用的，所以在這一點需要有所注意，
總而言之，使用遞回來書寫程式邏輯其實是比較簡單的，這個特點在非線性結構中，比如樹、圖這些資料結構，這個特點會體現地十分明顯，
小結
此時，對于遞回和鏈表中的遞回性質在使用了一個陣列求和的例子和 LeetCode 上的一道題目的例子做了相應的程序分析之后已經有了充分的了解，也發現了使用遞回來書寫邏輯是非常簡單易讀的，相比之前使用非遞回方式實作的題解其中的代碼，遞回方式的代碼只有短短幾行，但是相對應的，遞回也是有一定的局限性的，在使用的程序中需要注意系統堆疊空間的占有，如果資料量太大很可能會撐爆系統堆疊空間，所以這一方面需要額外注意，
如有寫的不足的，請見諒，請大家多多指教，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/143969.html
標籤：其他
上一篇：詳細分析堆疊和佇列的資料結構的實作程序（Java 實作）
下一篇：Meandering array