前言

給定一個單向鏈表的頭節點，如何獲取該鏈表中倒數第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。

遍歷一次鏈表

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

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

實現代碼

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

首先，我們設計一個名為GetLinkedListNode的類：

• 內部有2個私有變量。

pNext P1指針；

pHead P2指針。

• 構造方法接受1個參數：鏈表頭節點。

對參數進行校驗；

修改兩個指針的指向：默認指向鏈表頭節點。

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個節點。

// 獲取倒數第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：我們在寫代碼的時候，一定要盡可能地考慮各種邊界情況的處理，最大程度的避免一些錯誤的發生，提升代碼的健壯性。

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

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

測試用例

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

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);

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

完整代碼請移步：GetLinkedListNode-test.ts。

注意：上述代碼中用到的LinkedList是自定義的一個類，它實現了鏈表這個數據結構。

示例代碼

本文所列舉的代碼，其完整版請移步：

• GetLinkedListNode.ts
• GetLinkedListNode-test.ts