聊聊刪除鏈表中的重復(fù)節(jié)點，你會嗎？
常規(guī)思路
根據(jù)題意，我們可以知道鏈表中的元素是排好序的。如果節(jié)點重復(fù)的話，當(dāng)前節(jié)點一定與下一個節(jié)點相同。那么，我們只需要從第一個元素開始向后比對每個元素，修改節(jié)點的指針至不重復(fù)的節(jié)點，即可完成對重復(fù)節(jié)點的刪除。
大體思路有了，我們來梳理下實現(xiàn)思路：
- 首先，我們需要在鏈表的頭節(jié)點之前再創(chuàng)建一個節(jié)點將它命名為head，用于處理第一個節(jié)點與第二節(jié)點相同的情況。
- 其次，我們需要創(chuàng)建兩個指針：
一個指向當(dāng)前不重復(fù)的節(jié)點，我們將它命名為pre
一個為搜索指針，用于搜索鏈表中與當(dāng)前節(jié)點不重復(fù)的節(jié)點，我們將它命名為last
- 隨后，我們?yōu)?pre 與 last 進行初始賦值：
pre 指向head
last 指向head.next
- 緊接著，我們通過while循環(huán)訪問鏈表的每一個節(jié)點
修改pre的指針，將其指向其節(jié)點的下一個節(jié)點
修改last的指針，將其指向其節(jié)點的下一個節(jié)點
繼續(xù)通過while循環(huán)來訪問last的下一個節(jié)點，將當(dāng)前節(jié)點與其下一個節(jié)點進行比對，直至找到不重復(fù)的節(jié)點
找到不重復(fù)的節(jié)點后，我們修改pre的下一個節(jié)點，將其指向這個不重復(fù)的節(jié)點。
修改last的指針，將其指向其下一個節(jié)點，繼續(xù)向后探索。
last存在下一個節(jié)點且last節(jié)點的值與其下一個節(jié)點的值相等時：
否則就繼續(xù)向后探索：
- 最后，我們返回head節(jié)點的下一個節(jié)點。(因為head的節(jié)點本身是我們創(chuàng)建的輔助節(jié)點，其下一個節(jié)點才是我們修改完后的節(jié)點)
接下來，我們通過文章開頭所舉的例子，將其代入上述思路，畫一個圖來幫助大家更好的理解上述思路，如下所示：
實現(xiàn)代碼
接下來，我們將上述思路轉(zhuǎn)換為代碼，如下所示：
/**
* 刪除鏈表中的重復(fù)節(jié)點
* @param pHead 鏈表頭節(jié)點
*/
deleteDuplicatesNode(pHead: ListNode | null): ListNode | null {
if (pHead == null || pHead.next == null) return pHead;
// 創(chuàng)建一個頭節(jié)點,處理第一個與第二個節(jié)點相同的情況
const head: ListNode = { element: 0, next: pHead };
// 創(chuàng)建兩個指針: pre指向當(dāng)前不重復(fù)的節(jié)點，last為搜索指針一直向后探索尋找與當(dāng)前節(jié)點不重復(fù)的節(jié)點
let pre = head;
let last = head.next;
while (last != null) {
if (last.next != null && last.element === last.next.element) {
// 向后尋找不重復(fù)的節(jié)點
while (last.next != null && last.element === last.next.element) {
last = last.next;
}
// 將pre的指針指向不重復(fù)的節(jié)點上
pre.next = last.next;
// 繼續(xù)向后探索
last = last.next;
} else {
// 將指針指向其節(jié)點的下一個節(jié)點, 繼續(xù)向后探索
pre = <ListNode>pre.next;
last = last.next;
}
}
return head.next;
}
上述代碼中的ListNode為自定義類型，具體的代碼請在本文的示例代碼章節(jié)查看。
測試用例
最后，我們將開頭的例子代入上述代碼，驗證下能否正確執(zhí)行。
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());
// 輸出修改后的鏈表節(jié)點
printListNode(pHead);
執(zhí)行結(jié)果如下圖所示：
注意：printListNode用于按序輸出鏈表中的每個節(jié)點，具體的代碼請在本文的示例代碼章節(jié)查看。
遞歸思路
接下來，我們換一種思路來解決這個問題，如果當(dāng)前節(jié)點pHead與它的下一個節(jié)點相等，我們就通過新增一個指針的方式，使用while循環(huán)修改其指向，直至找到與pHead不同的節(jié)點。找到后，我們將其傳入遞歸函數(shù)，并返回這個遞歸函數(shù);如果當(dāng)前節(jié)點pHead與它的下一個節(jié)點不等，我們就將其下一個節(jié)點的傳入遞歸函數(shù)，修改pHead的下一個節(jié)點指向為此遞歸函數(shù)。最后，我們返回pHead節(jié)點。
我們來梳理下上述思路：
- 確定遞歸基線條件：pHead或者pHead.next為null
- 比對當(dāng)前節(jié)點pHead與其下一個節(jié)點pHead.next：
如果相等，創(chuàng)建一個臨時指針，通過while循環(huán)繼續(xù)向后探索，尋找與當(dāng)前節(jié)點不重復(fù)的節(jié)點;找到后繼續(xù)調(diào)用遞歸函數(shù)，將不重復(fù)的節(jié)點作為參數(shù)傳入，最后返回這個遞歸函數(shù)。
如果不相等，則修改pHead.next指向，使用遞歸函數(shù)求出當(dāng)前不相等的節(jié)點，最后返回pHead。
我們將文章開頭所舉的例子，代入上述思路，畫一下它的遞歸棧幫助大家更好的理解，如下所示：
實現(xiàn)代碼
接下來，我們將上述思路轉(zhuǎn)換為代碼，如下所示：
/**
* 刪除鏈表中的重復(fù)節(jié)點(遞歸解法)
* @param pHead 鏈表頭節(jié)點
*/
deleteDuplicatesNodeForRecursion(pHead: ListNode | null): ListNode | null {
// 節(jié)點不存在或只有1個節(jié)點時直接返回
if (pHead == null || pHead.next == null) return pHead;
// 當(dāng)前節(jié)點是重復(fù)節(jié)點
if (pHead.element === pHead.next.element) {
let pNode: ListNode | null = pHead.next;
// 通過遍歷，找到第一個與當(dāng)前節(jié)點不同的節(jié)點
while (pNode != null && pNode.element === pHead.element) {
// 尋找第一個與當(dāng)前節(jié)點不同的節(jié)點
pNode = pNode.next;
}
// 本輪遞歸結(jié)束，從第一個與當(dāng)前節(jié)點不同的節(jié)點開始遞歸
return this.deleteDuplicatesNodeForRecursion(pNode);
} else {
// 連接不重復(fù)的節(jié)點
pHead.next = this.deleteDuplicatesNodeForRecursion(pHead.next);
// 本輪輪遞歸結(jié)束，返回最終的鏈表頭節(jié)點
return pHead;
}
}
測試用例
我們將開頭的例子代入上述代碼，驗證下能否正確執(zhí)行。
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()
);
// 輸出修改后的鏈表節(jié)點
console.log("刪除重復(fù)節(jié)點后，鏈表的剩余節(jié)點為: ");
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
