常規(guī)思路

根據(jù)題意，我們可以知道鏈表中的元素是排好序的。如果節(jié)點(diǎn)重復(fù)的話，當(dāng)前節(jié)點(diǎn)一定與下一個(gè)節(jié)點(diǎn)相同。那么，我們只需要從第一個(gè)元素開始向后比對(duì)每個(gè)元素，修改節(jié)點(diǎn)的指針至不重復(fù)的節(jié)點(diǎn)，即可完成對(duì)重復(fù)節(jié)點(diǎn)的刪除。

大體思路有了，我們來(lái)梳理下實(shí)現(xiàn)思路：

• 首先，我們需要在鏈表的頭節(jié)點(diǎn)之前再創(chuàng)建一個(gè)節(jié)點(diǎn)將它命名為head，用于處理第一個(gè)節(jié)點(diǎn)與第二節(jié)點(diǎn)相同的情況。
• 其次，我們需要?jiǎng)?chuàng)建兩個(gè)指針：

一個(gè)指向當(dāng)前不重復(fù)的節(jié)點(diǎn)，我們將它命名為pre

一個(gè)為搜索指針，用于搜索鏈表中與當(dāng)前節(jié)點(diǎn)不重復(fù)的節(jié)點(diǎn)，我們將它命名為last

• 隨后，我們?yōu)?pre 與 last 進(jìn)行初始賦值：

pre 指向head

last 指向head.next

• 緊接著，我們通過(guò)while循環(huán)訪問(wèn)鏈表的每一個(gè)節(jié)點(diǎn)

修改pre的指針，將其指向其節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)

修改last的指針，將其指向其節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)

繼續(xù)通過(guò)while循環(huán)來(lái)訪問(wèn)last的下一個(gè)節(jié)點(diǎn)，將當(dāng)前節(jié)點(diǎn)與其下一個(gè)節(jié)點(diǎn)進(jìn)行比對(duì)，直至找到不重復(fù)的節(jié)點(diǎn)

找到不重復(fù)的節(jié)點(diǎn)后，我們修改pre的下一個(gè)節(jié)點(diǎn)，將其指向這個(gè)不重復(fù)的節(jié)點(diǎn)。

修改last的指針，將其指向其下一個(gè)節(jié)點(diǎn)，繼續(xù)向后探索。

last存在下一個(gè)節(jié)點(diǎn)且last節(jié)點(diǎn)的值與其下一個(gè)節(jié)點(diǎn)的值相等時(shí)：

否則就繼續(xù)向后探索：

• 最后，我們返回head節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。(因?yàn)閔ead的節(jié)點(diǎn)本身是我們創(chuàng)建的輔助節(jié)點(diǎn)，其下一個(gè)節(jié)點(diǎn)才是我們修改完后的節(jié)點(diǎn))

接下來(lái)，我們通過(guò)文章開頭所舉的例子，將其代入上述思路，畫一個(gè)圖來(lái)幫助大家更好的理解上述思路，如下所示：

實(shí)現(xiàn)代碼

接下來(lái)，我們將上述思路轉(zhuǎn)換為代碼，如下所示：

  /**
   * 刪除鏈表中的重復(fù)節(jié)點(diǎn)
   * @param pHead 鏈表頭節(jié)點(diǎn)
   */
  deleteDuplicatesNode(pHead: ListNode | null): ListNode | null {
    if (pHead == null || pHead.next == null) return pHead;
    // 創(chuàng)建一個(gè)頭節(jié)點(diǎn),處理第一個(gè)與第二個(gè)節(jié)點(diǎn)相同的情況
    const head: ListNode = { element: 0, next: pHead };
    // 創(chuàng)建兩個(gè)指針: pre指向當(dāng)前不重復(fù)的節(jié)點(diǎn)，last為搜索指針一直向后探索尋找與當(dāng)前節(jié)點(diǎn)不重復(fù)的節(jié)點(diǎn)
    let pre = head;
    let last = head.next;
    while (last != null) {
      if (last.next != null && last.element === last.next.element) {
        // 向后尋找不重復(fù)的節(jié)點(diǎn)
        while (last.next != null && last.element === last.next.element) {
          last = last.next;
        }
        // 將pre的指針指向不重復(fù)的節(jié)點(diǎn)上
        pre.next = last.next;
        // 繼續(xù)向后探索
        last = last.next;
      } else {
        // 將指針指向其節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn), 繼續(xù)向后探索
        pre = <ListNode>pre.next;
        last = last.next;
      }
    }
    return head.next;
  }

上述代碼中的ListNode為自定義類型，具體的代碼請(qǐng)?jiān)诒疚牡氖纠a章節(jié)查看。

測(cè)試用例

最后，我們將開頭的例子代入上述代碼，驗(yàn)證下能否正確執(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é)點(diǎn)
printListNode(pHead);

執(zhí)行結(jié)果如下圖所示：

注意：printListNode用于按序輸出鏈表中的每個(gè)節(jié)點(diǎn)，具體的代碼請(qǐng)?jiān)诒疚牡氖纠a章節(jié)查看。

遞歸思路

接下來(lái)，我們換一種思路來(lái)解決這個(gè)問(wèn)題，如果當(dāng)前節(jié)點(diǎn)pHead與它的下一個(gè)節(jié)點(diǎn)相等，我們就通過(guò)新增一個(gè)指針的方式，使用while循環(huán)修改其指向，直至找到與pHead不同的節(jié)點(diǎn)。找到后，我們將其傳入遞歸函數(shù)，并返回這個(gè)遞歸函數(shù);如果當(dāng)前節(jié)點(diǎn)pHead與它的下一個(gè)節(jié)點(diǎn)不等，我們就將其下一個(gè)節(jié)點(diǎn)的傳入遞歸函數(shù)，修改pHead的下一個(gè)節(jié)點(diǎn)指向?yàn)榇诉f歸函數(shù)。最后，我們返回pHead節(jié)點(diǎn)。

我們來(lái)梳理下上述思路：

• 確定遞歸基線條件：pHead或者pHead.next為null
• 比對(duì)當(dāng)前節(jié)點(diǎn)pHead與其下一個(gè)節(jié)點(diǎn)pHead.next：

如果相等，創(chuàng)建一個(gè)臨時(shí)指針，通過(guò)while循環(huán)繼續(xù)向后探索，尋找與當(dāng)前節(jié)點(diǎn)不重復(fù)的節(jié)點(diǎn);找到后繼續(xù)調(diào)用遞歸函數(shù)，將不重復(fù)的節(jié)點(diǎn)作為參數(shù)傳入，最后返回這個(gè)遞歸函數(shù)。

如果不相等，則修改pHead.next指向，使用遞歸函數(shù)求出當(dāng)前不相等的節(jié)點(diǎn)，最后返回pHead。

我們將文章開頭所舉的例子，代入上述思路，畫一下它的遞歸棧幫助大家更好的理解，如下所示：

實(shí)現(xiàn)代碼

接下來(lái)，我們將上述思路轉(zhuǎn)換為代碼，如下所示：

  /**
   * 刪除鏈表中的重復(fù)節(jié)點(diǎn)(遞歸解法)
   * @param pHead 鏈表頭節(jié)點(diǎn)
   */
  deleteDuplicatesNodeForRecursion(pHead: ListNode | null): ListNode | null {
    // 節(jié)點(diǎn)不存在或只有1個(gè)節(jié)點(diǎn)時(shí)直接返回
    if (pHead == null || pHead.next == null) return pHead;
    // 當(dāng)前節(jié)點(diǎn)是重復(fù)節(jié)點(diǎn)
    if (pHead.element === pHead.next.element) {
      let pNode: ListNode | null = pHead.next;
      // 通過(guò)遍歷，找到第一個(gè)與當(dāng)前節(jié)點(diǎn)不同的節(jié)點(diǎn)
      while (pNode != null && pNode.element === pHead.element) {
        // 尋找第一個(gè)與當(dāng)前節(jié)點(diǎn)不同的節(jié)點(diǎn)
        pNode = pNode.next;
      }
      // 本輪遞歸結(jié)束，從第一個(gè)與當(dāng)前節(jié)點(diǎn)不同的節(jié)點(diǎn)開始遞歸
      return this.deleteDuplicatesNodeForRecursion(pNode);
    } else {
      // 連接不重復(fù)的節(jié)點(diǎn)
      pHead.next = this.deleteDuplicatesNodeForRecursion(pHead.next);
      // 本輪輪遞歸結(jié)束，返回最終的鏈表頭節(jié)點(diǎn)
      return pHead;
    }
  }

測(cè)試用例

我們將開頭的例子代入上述代碼，驗(yàn)證下能否正確執(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é)點(diǎn)
console.log("刪除重復(fù)節(jié)點(diǎn)后，鏈表的剩余節(jié)點(diǎn)為: ");
printListNode(pHead);

示例代碼

本文實(shí)例的完整代碼如下：

• 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