獲取鏈表中倒數第K個節點

語言: CN / TW / HK

前言

給定一個單向鏈表的頭節點,如何獲取該鏈表中倒數第K個節點(從1開始計數)?本文將帶着大家一起解決這個問題,歡迎各位感興趣的開發者閲讀本文。

思路分析

我們通過一個例子來做進一步的分析:

  • 準備一個鏈表,它有6個節點,從頭節點開始,其值依次為:1、3、5、9、15、21

  • 獲取該鏈表的倒數第3個節點

遍歷兩次鏈表

根據單向鏈表的定義,我們可知:想要獲取它的某個節點,只能從頭節點開始順着其指針往後查找。假設整個鏈表有n個節點,那麼倒數第K個節點就是從頭節點開始的第n-K+1個節點。如果我們能夠得到節點數n,那麼只需要從頭節點開始往後走n-k+1步就可以了。想要得到節點數n,就需要定義一個變量,從頭開始遍歷鏈表,每經過一個節點,這個變量就自增1。

也就是説,我們需要遍歷鏈表兩次,第一次計算出鏈表中節點的個數,第二次就能獲取倒數第K個節點,如下圖所示:

  • 第1次遍歷鏈表拿到了鏈表的長度n=6
  • 第2次遍歷鏈表獲取到了倒數第3個節點處(6-3+1)的值9

IMG_498E0908B970-1

遍歷一次鏈表

遍歷兩次鏈表來解決這個問題並不是最優解,我們換個思路來考慮下這個問題:準備兩個指針。

  • 第一個指針從鏈表的頭部開始遍歷向前走k-1(3-1=2)步,第二個指針保持不動
  • 從第k步開始,第二個指針也開始從鏈表的頭指針開始遍歷,兩指針同時向前走。
  • 由於兩個指針的距離始終保持在k-1,當第一個指針到達鏈表的尾節點時,第二個指針正好指向倒數第k個節點

IMG_596AE88489E9-1 2

實現代碼

通過上面的分析,我們知道了如何用雙指針的思路,只遍歷一次鏈表就能獲取鏈表的倒數第K個節點。接下來,我們來看下代碼實現。

首先,我們設計一個名為GetLinkedListNode的類:

  • 內部有2個私有變量
  • pNext P1指針
  • pHead P2指針
  • 構造方法接受1個參數:鏈表頭節點
  • 對參數進行校驗
  • 修改兩個指針的指向:默認指向鏈表頭節點

```typescript export class GetLinkedListNode { // p1指針 private pNext: ListNode; // p2指針(與p1指針的距離始終保持在k-1) private pHead: ListNode;

constructor(listHead: ListNode) { if (listHead == null) { throw new Error("鏈表頭節點不能為空"); }

// 初始化兩個指針指向
this.pNext = listHead;
this.pHead = listHead;

} ```

上述代碼中,我們用了一個自定義類型ListNode,它描述了一個鏈表的節點應該包含哪些屬性,對此感興趣的開發者請移步我的另一篇文章:鏈表與變相鏈表的實現

緊接着,實現獲取倒數第K個節點函數:

  • 接受一個參數K(從1開始),對參數進行有效性校驗
  • 修改p1指針的指向,將其指向k-1節點,k的範圍也要做一下規避處理(其值大於鏈表總節點數)
  • 同步修改p1、p2指針的指向,直至p1指針指向尾節點,p2指針正好指向倒數第K個節點

```typescript // 獲取倒數第K個節點 getCountdownNode(k: number): ListNode { if (k <= 0) { throw new Error("需要獲取的倒數節點數必須大於0"); }

// p1指針先走,將其指向鏈表的k-1位置
for (let i = 0; i < k - 1; i++) {
  // k可能出現大於鏈表總節點的情況,需要進行規避
  if (this.pNext.next != null) {
    this.pNext = this.pNext.next;
  } else {
    throw new Error("需要找的節點不存在");
  }
}

// 兩個指針同時向前走,直至p1指針指向尾節點
while (this.pNext.next) {
  this.pNext = this.pNext.next;
  if (this.pHead.next) {
    this.pHead = this.pHead.next;
  }
}

// p2節點正好指向倒數第K個節點
return this.pHead;

} ```

完整代碼請移步👉:GetLinkedListNode.ts

小tips:我們在寫代碼的時候,一定要儘可能地考慮各種邊界情況的處理,最大程度的避免一些錯誤的發生,提升代碼的健壯性。

例如上述代碼中所做的處理,最大程度的避免了程序因取不到值而引發的異常報錯問題,我們也管這種做法稱為防禦性編程

這是一種良好的編程習慣,在編寫代碼的時候多問問自己“如果不······那麼······”這樣的問題,提前預見在什麼地方可能會出現問題,併為這些可能出現的問題制定處理方式。這樣,當異常情況發生時,軟件的行為也盡在我們的掌握之中,而不至於出現不可預見的事情。

測試用例

接下來,我們將前言中的例子代入上個章節所實現的函數中,驗證下它能否得出正確的結果。

```typescript const linkedList = new LinkedList(); linkedList.push(1); linkedList.push(3); linkedList.push(5); linkedList.push(9); linkedList.push(15); linkedList.push(21);

const getLinkedListNode = new GetLinkedListNode(linkedList.getHead()); const resultNode = getLinkedListNode.getCountdownNode(3); console.log(resultNode);

```

運行結果如下所示,成功的解決了文章前言中所講的問題。

image-20220531223219124

完整代碼請移步👉:GetLinkedListNode-test.ts

注意:上述代碼中用到的LinkedList是自定義的一個類,它實現了鏈表這個數據結構,對其原理感興趣的開發者請移步我的另一篇文章👉:鏈表與變相鏈表的實現

示例代碼

本文所列舉的代碼,其完整版請移步👇:

寫在最後

至此,文章就分享完畢了。

我是神奇的程序員,一位前端開發工程師。

如果你對我感興趣,請移步我的個人網站,進一步瞭解。

  • 文中如有錯誤,歡迎在評論區指正,如果這篇文章幫到了你,歡迎點贊和關注😊
  • 本文首發於神奇的程序員公眾號,未經許可禁止轉載💌