聊聊刪除鏈表中的重復節點，你會嗎？
常規思路
根據題意，我們可以知道鏈表中的元素是排好序的。如果節點重復的話，當前節點一定與下一個節點相同。那么，我們只需要從第一個元素開始向后比對每個元素，修改節點的指針至不重復的節點，即可完成對重復節點的刪除。
大體思路有了，我們來梳理下實現思路：
- 首先，我們需要在鏈表的頭節點之前再創建一個節點將它命名為head，用于處理第一個節點與第二節點相同的情況。
- 其次，我們需要創建兩個指針：
一個指向當前不重復的節點，我們將它命名為pre
一個為搜索指針，用于搜索鏈表中與當前節點不重復的節點，我們將它命名為last
- 隨后，我們為 pre 與 last 進行初始賦值：
pre 指向head
last 指向head.next
- 緊接著，我們通過while循環訪問鏈表的每一個節點
修改pre的指針，將其指向其節點的下一個節點
修改last的指針，將其指向其節點的下一個節點
繼續通過while循環來訪問last的下一個節點，將當前節點與其下一個節點進行比對，直至找到不重復的節點
找到不重復的節點后，我們修改pre的下一個節點，將其指向這個不重復的節點。
修改last的指針，將其指向其下一個節點，繼續向后探索。
last存在下一個節點且last節點的值與其下一個節點的值相等時：
否則就繼續向后探索：
- 最后，我們返回head節點的下一個節點。(因為head的節點本身是我們創建的輔助節點，其下一個節點才是我們修改完后的節點)
接下來，我們通過文章開頭所舉的例子，將其代入上述思路，畫一個圖來幫助大家更好的理解上述思路，如下所示：
實現代碼
接下來，我們將上述思路轉換為代碼，如下所示：
/**
* 刪除鏈表中的重復節點
* @param pHead 鏈表頭節點
*/
deleteDuplicatesNode(pHead: ListNode | null): ListNode | null {
if (pHead == null || pHead.next == null) return pHead;
// 創建一個頭節點,處理第一個與第二個節點相同的情況
const head: ListNode = { element: 0, next: pHead };
// 創建兩個指針: pre指向當前不重復的節點，last為搜索指針一直向后探索尋找與當前節點不重復的節點
let pre = head;
let last = head.next;
while (last != null) {
if (last.next != null && last.element === last.next.element) {
// 向后尋找不重復的節點
while (last.next != null && last.element === last.next.element) {
last = last.next;
}
// 將pre的指針指向不重復的節點上
pre.next = last.next;
// 繼續向后探索
last = last.next;
} else {
// 將指針指向其節點的下一個節點, 繼續向后探索
pre = <ListNode>pre.next;
last = last.next;
}
}
return head.next;
}
上述代碼中的ListNode為自定義類型，具體的代碼請在本文的示例代碼章節查看。
測試用例
最后，我們將開頭的例子代入上述代碼，驗證下能否正確執行。
import { DeleteLinkedListNode } from "../DeleteLinkedListNode.ts";
import LinkedList from "../lib/LinkedList.ts";
import { printListNode } from "../utils/linked-list-models.ts";
const listNode = new LinkedList();
listNode.push(1);
listNode.push(2);
listNode.push(3);
listNode.push(3);
listNode.push(4);
listNode.push(4);
listNode.push(5);
const pHead = deleteLinkedListNode.deleteDuplicatesNode(listNode.getHead());
// 輸出修改后的鏈表節點
printListNode(pHead);
執行結果如下圖所示：
注意：printListNode用于按序輸出鏈表中的每個節點，具體的代碼請在本文的示例代碼章節查看。
遞歸思路
接下來，我們換一種思路來解決這個問題，如果當前節點pHead與它的下一個節點相等，我們就通過新增一個指針的方式，使用while循環修改其指向，直至找到與pHead不同的節點。找到后，我們將其傳入遞歸函數，并返回這個遞歸函數;如果當前節點pHead與它的下一個節點不等，我們就將其下一個節點的傳入遞歸函數，修改pHead的下一個節點指向為此遞歸函數。最后，我們返回pHead節點。
我們來梳理下上述思路：
- 確定遞歸基線條件：pHead或者pHead.next為null
- 比對當前節點pHead與其下一個節點pHead.next：
如果相等，創建一個臨時指針，通過while循環繼續向后探索，尋找與當前節點不重復的節點;找到后繼續調用遞歸函數，將不重復的節點作為參數傳入，最后返回這個遞歸函數。
如果不相等，則修改pHead.next指向，使用遞歸函數求出當前不相等的節點，最后返回pHead。
我們將文章開頭所舉的例子，代入上述思路，畫一下它的遞歸棧幫助大家更好的理解，如下所示：
實現代碼
接下來，我們將上述思路轉換為代碼，如下所示：
/**
* 刪除鏈表中的重復節點(遞歸解法)
* @param pHead 鏈表頭節點
*/
deleteDuplicatesNodeForRecursion(pHead: ListNode | null): ListNode | null {
// 節點不存在或只有1個節點時直接返回
if (pHead == null || pHead.next == null) return pHead;
// 當前節點是重復節點
if (pHead.element === pHead.next.element) {
let pNode: ListNode | null = pHead.next;
// 通過遍歷，找到第一個與當前節點不同的節點
while (pNode != null && pNode.element === pHead.element) {
// 尋找第一個與當前節點不同的節點
pNode = pNode.next;
}
// 本輪遞歸結束，從第一個與當前節點不同的節點開始遞歸
return this.deleteDuplicatesNodeForRecursion(pNode);
} else {
// 連接不重復的節點
pHead.next = this.deleteDuplicatesNodeForRecursion(pHead.next);
// 本輪輪遞歸結束，返回最終的鏈表頭節點
return pHead;
}
}
測試用例
我們將開頭的例子代入上述代碼，驗證下能否正確執行。
import { DeleteLinkedListNode } from "../DeleteLinkedListNode.ts";
import LinkedList from "../lib/LinkedList.ts";
import { printListNode } from "../utils/linked-list-models.ts";
listNode = new LinkedList();
listNode.push(1);
listNode.push(2);
listNode.push(3);
listNode.push(3);
listNode.push(4);
listNode.push(4);
listNode.push(5);
const pHead = deleteLinkedListNode.deleteDuplicatesNodeForRecursion(
listNode.getHead()
);
// 輸出修改后的鏈表節點
console.log("刪除重復節點后，鏈表的剩余節點為: ");
printListNode(pHead);
示例代碼
本文實例的完整代碼如下：
- DeleteLinkedListNode.ts[1]
- deleteLinkedListNode-test.ts[2]
- LinkedList.ts[3]
- linked-list-models.ts[4]
參考資料
[1]DeleteLinkedListNode.ts: https://github.com/likaia/algorithm-practice/blob/67dff903c1dafce96f9b7e50d9f063b25eb01c5a/src/DeleteLinkedListNode.ts#L36
[2]deleteLinkedListNode-test.ts: https://github.com/likaia/algorithm-practice/blob/67dff903c1dafce96f9b7e50d9f063b25eb01c5a/src/test-case/deleteLinkedListNode-test.ts#L34
[3]LinkedList.ts: https://github.com/likaia/algorithm-practice/blob/212a5351f662ddf48bab2c289194bb09c378d9a1/src/lib/LinkedList.ts#L9
[4]linked-list-models.ts: https://github.com/likaia/algorithm-practice/blob/67dff903c1dafce96f9b7e50d9f063b25eb01c5a/src/utils/linked-list-models.ts#L29
