刪除鏈表中的重復節(jié)點-掘金.png

前言

在一個排序的鏈表中激才，存在重復的節(jié)點瘸恼，如何刪除鏈表中重復的節(jié)點并返回刪除后的鏈表頭指針东帅？例如：1->2->3->3->4->4->5靠闭，處理后為: 1->2->5坎炼。

本文將分享這個問題的解決思路與實現(xiàn)代碼谣光，歡迎各位感興趣的開發(fā)者閱讀本文。

常規(guī)思路

根據(jù)題意蟀悦，我們可以知道鏈表中的元素是排好序的日戈。如果節(jié)點重復的話涎拉，當前節(jié)點一定與下一個節(jié)點相同。那么鼓拧，我們只需要從第一個元素開始向后比對每個元素钮糖，修改節(jié)點的指針至不重復的節(jié)點酌住，即可完成對重復節(jié)點的刪除酪我。

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

• 首先秩伞，我們需要在鏈表的頭節(jié)點之前再創(chuàng)建一個節(jié)點將它命名為head纱新，用于處理第一個節(jié)點與第二節(jié)點相同的情況脸爱。

• 其次簿废，我們需要創(chuàng)建兩個指針：

  • 一個指向當前不重復的節(jié)點，我們將它命名為pre
  • 一個為搜索指針捏鱼，用于搜索鏈表中與當前節(jié)點不重復的節(jié)點，我們將它命名為last

• 隨后轨淌，我們?yōu)?pre 與 last 進行初始賦值：

  • pre 指向head
  • last 指向head.next

• 緊接著递鹉，我們通過while循環(huán)訪問鏈表的每一個節(jié)點

  • last存在下一個節(jié)點且last節(jié)點的值與其下一個節(jié)點的值相等時：
    • 繼續(xù)通過while循環(huán)來訪問last的下一個節(jié)點躏结，將當前節(jié)點與其下一個節(jié)點進行比對，直至找到不重復的節(jié)點
    • 找到不重復的節(jié)點后兆览，我們修改pre的下一個節(jié)點抬探，將其指向這個不重復的節(jié)點小压。
    • 修改last的指針椰于，將其指向其下一個節(jié)點瘾婿，繼續(xù)向后探索憋他。
  • 否則就繼續(xù)向后探索：
    • 修改pre的指針竹挡，將其指向其節(jié)點的下一個節(jié)點
    • 修改last的指針揪罕，將其指向其節(jié)點的下一個節(jié)點

• 最后好啰，我們返回head節(jié)點的下一個節(jié)點。（因為head的節(jié)點本身是我們創(chuàng)建的輔助節(jié)點鳄抒，其下一個節(jié)點才是我們修改完后的節(jié)點）

接下來许溅，我們通過文章開頭所舉的例子贤重，將其代入上述思路并蝗，畫一個圖來幫助大家更好的理解上述思路，如下所示：

image-20220226224625702

實現(xiàn)代碼

接下來沃粗，我們將上述思路轉換為代碼陪每，如下所示：

  /**
   * 刪除鏈表中的重復節(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指向當前不重復的節(jié)點，last為搜索指針一直向后探索尋找與當前節(jié)點不重復的節(jié)點
    let pre = head;
    let last = head.next;
    while (last != null) {
      if (last.next != null && last.element === last.next.element) {
        // 向后尋找不重復的節(jié)點
        while (last.next != null && last.element === last.next.element) {
          last = last.next;
        }
        // 將pre的指針指向不重復的節(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í)行結果如下圖所示：

image-20220226230022928

注意：printListNode用于按序輸出鏈表中的每個節(jié)點炉奴，具體的代碼請在本文的示例代碼章節(jié)查看。

遞歸思路

接下來共耍，我們換一種思路來解決這個問題，如果當前節(jié)點pHead與它的下一個節(jié)點相等吨瞎，我們就通過新增一個指針的方式，使用while循環(huán)修改其指向穆咐，直至找到與pHead不同的節(jié)點颤诀。找到后字旭，我們將其傳入遞歸函數(shù)，并返回這個遞歸函數(shù)崖叫；如果當前節(jié)點pHead與它的下一個節(jié)點不等遗淳，我們就將其下一個節(jié)點的傳入遞歸函數(shù)，修改pHead的下一個節(jié)點指向為此遞歸函數(shù)心傀。最后屈暗，我們返回pHead節(jié)點。

我們來梳理下上述思路：

• 確定遞歸基線條件：pHead或者pHead.next為null
• 比對當前節(jié)點pHead與其下一個節(jié)點pHead.next：
  • 如果相等脂男，創(chuàng)建一個臨時指針养叛，通過while循環(huán)繼續(xù)向后探索，尋找與當前節(jié)點不重復的節(jié)點；找到后繼續(xù)調用遞歸函數(shù)瓶珊，將不重復的節(jié)點作為參數(shù)傳入搜囱，最后返回這個遞歸函數(shù)。
  • 如果不相等，則修改pHead.next指向，使用遞歸函數(shù)求出當前不相等的節(jié)點，最后返回pHead楣颠。

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

image-20220228231355965

實現(xiàn)代碼

接下來，我們將上述思路轉換為代碼，如下所示：

  /**
   * 刪除鏈表中的重復節(jié)點(遞歸解法)
   * @param pHead 鏈表頭節(jié)點
   */
  deleteDuplicatesNodeForRecursion(pHead: ListNode | null): ListNode | null {
    // 節(jié)點不存在或只有1個節(jié)點時直接返回
    if (pHead == null || pHead.next == null) return pHead;
    // 當前節(jié)點是重復節(jié)點
    if (pHead.element === pHead.next.element) {
      let pNode: ListNode | null = pHead.next;
      // 通過遍歷挖胃，找到第一個與當前節(jié)點不同的節(jié)點
      while (pNode != null && pNode.element === pHead.element) {
        // 尋找第一個與當前節(jié)點不同的節(jié)點
        pNode = pNode.next;
      }
      // 本輪遞歸結束垛吗，從第一個與當前節(jié)點不同的節(jié)點開始遞歸
      return this.deleteDuplicatesNodeForRecursion(pNode);
    } else {
      // 連接不重復的節(jié)點
      pHead.next = this.deleteDuplicatesNodeForRecursion(pHead.next);
      // 本輪輪遞歸結束，返回最終的鏈表頭節(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("刪除重復節(jié)點后狼犯，鏈表的剩余節(jié)點為: ");
printListNode(pHead);

image-20220228233449946

示例代碼

本文實例的完整代碼如下：

• DeleteLinkedListNode.ts
• deleteLinkedListNode-test.ts
• LinkedList.ts
• linked-list-models.ts

寫在最后

至此幻碱，文章就分享完畢了喇聊。

我是神奇的程序員，一位前端開發(fā)工程師。

如果你對我感興趣，請移步我的個人網(wǎng)站，進一步了解。

• 文中如有錯誤盏缤，歡迎在評論區(qū)指正，如果這篇文章幫到了你，歡迎點贊和關注??
• 本文首發(fā)于神奇的程序員公眾號股耽，未經許可禁止轉載??