前言

給定一個(gè)單向鏈表的頭節(jié)點(diǎn)，如何獲取該鏈表中倒數(shù)第K個(gè)節(jié)點(diǎn)(從1開始計(jì)數(shù))?本文將帶著大家一起解決這個(gè)問題，歡迎各位感興趣的開發(fā)者閱讀本文。

思路分析

我們通過一個(gè)例子來做進(jìn)一步的分析：

• 準(zhǔn)備一個(gè)鏈表，它有6個(gè)節(jié)點(diǎn)，從頭節(jié)點(diǎn)開始，其值依次為：1、3、5、9、15、21。
• 獲取該鏈表的倒數(shù)第3個(gè)節(jié)點(diǎn)。

遍歷兩次鏈表

根據(jù)單向鏈表的定義，我們可知：想要獲取它的某個(gè)節(jié)點(diǎn)，只能從頭節(jié)點(diǎn)開始順著其指針往后查找。假設(shè)整個(gè)鏈表有n個(gè)節(jié)點(diǎn)，那么倒數(shù)第K個(gè)節(jié)點(diǎn)就是從頭節(jié)點(diǎn)開始的第n-K+1個(gè)節(jié)點(diǎn)。如果我們能夠得到節(jié)點(diǎn)數(shù)n，那么只需要從頭節(jié)點(diǎn)開始往后走n-k+1步就可以了。想要得到節(jié)點(diǎn)數(shù)n，就需要定義一個(gè)變量，從頭開始遍歷鏈表，每經(jīng)過一個(gè)節(jié)點(diǎn)，這個(gè)變量就自增1。

也就是說，我們需要遍歷鏈表兩次，第一次計(jì)算出鏈表中節(jié)點(diǎn)的個(gè)數(shù)，第二次就能獲取倒數(shù)第K個(gè)節(jié)點(diǎn)，如下圖所示：

• 第1次遍歷鏈表拿到了鏈表的長(zhǎng)度n=6。
• 第2次遍歷鏈表獲取到了倒數(shù)第3個(gè)節(jié)點(diǎn)處(6-3+1)的值9。

遍歷一次鏈表

遍歷兩次鏈表來解決這個(gè)問題并不是最優(yōu)解，我們換個(gè)思路來考慮下這個(gè)問題：準(zhǔn)備兩個(gè)指針。

• 第一個(gè)指針從鏈表的頭部開始遍歷向前走k-1(3-1=2)步，第二個(gè)指針保持不動(dòng)。
• 從第k步開始，第二個(gè)指針也開始從鏈表的頭指針開始遍歷，兩指針同時(shí)向前走。
• 由于兩個(gè)指針的距離始終保持在k-1，當(dāng)?shù)谝粋€(gè)指針到達(dá)鏈表的尾節(jié)點(diǎn)時(shí)，第二個(gè)指針正好指向倒數(shù)第k個(gè)節(jié)點(diǎn)。

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

通過上面的分析，我們知道了如何用雙指針的思路，只遍歷一次鏈表就能獲取鏈表的倒數(shù)第K個(gè)節(jié)點(diǎn)。接下來，我們來看下代碼實(shí)現(xiàn)。

首先，我們?cè)O(shè)計(jì)一個(gè)名為GetLinkedListNode的類：

• 內(nèi)部有2個(gè)私有變量。

pNext P1指針；

pHead P2指針。

• 構(gòu)造方法接受1個(gè)參數(shù)：鏈表頭節(jié)點(diǎn)。

對(duì)參數(shù)進(jìn)行校驗(yàn)；

修改兩個(gè)指針的指向：默認(rèn)指向鏈表頭節(jié)點(diǎn)。

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

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

    // 初始化兩個(gè)指針指向
    this.pNext = listHead;
    this.pHead = listHead;
}

上述代碼中，我們用了一個(gè)自定義類型ListNode，它描述了一個(gè)鏈表的節(jié)點(diǎn)應(yīng)該包含哪些屬性，對(duì)此感興趣的開發(fā)者請(qǐng)移步我的另一篇文章：鏈表與變相鏈表的實(shí)現(xiàn)。

緊接著，實(shí)現(xiàn)獲取倒數(shù)第K個(gè)節(jié)點(diǎn)函數(shù)：

• 接受一個(gè)參數(shù)K(從1開始)，對(duì)參數(shù)進(jìn)行有效性校驗(yàn)。
• 修改p1指針的指向，將其指向k-1節(jié)點(diǎn)，k的范圍也要做一下規(guī)避處理(其值大于鏈表總節(jié)點(diǎn)數(shù))。
• 同步修改p1、p2指針的指向，直至p1指針指向尾節(jié)點(diǎn)，p2指針正好指向倒數(shù)第K個(gè)節(jié)點(diǎn)。

// 獲取倒數(shù)第K個(gè)節(jié)點(diǎn)
  getCountdownNode(k: number): ListNode {
    if (k <= 0) {
      throw new Error("需要獲取的倒數(shù)節(jié)點(diǎn)數(shù)必須大于0");
    }

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

    // 兩個(gè)指針同時(shí)向前走，直至p1指針指向尾節(jié)點(diǎn)
    while (this.pNext.next) {
      this.pNext = this.pNext.next;
      if (this.pHead.next) {
        this.pHead = this.pHead.next;
      }
    }

    // p2節(jié)點(diǎn)正好指向倒數(shù)第K個(gè)節(jié)點(diǎn)
    return this.pHead;
  }

完整代碼請(qǐng)移步：GetLinkedListNode.ts。

小tips：我們?cè)趯懘a的時(shí)候，一定要盡可能地考慮各種邊界情況的處理，最大程度的避免一些錯(cuò)誤的發(fā)生，提升代碼的健壯性。

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

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

測(cè)試用例

接下來，我們將前言中的例子代入上個(gè)章節(jié)所實(shí)現(xiàn)的函數(shù)中，驗(yàn)證下它能否得出正確的結(jié)果。

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

運(yùn)行結(jié)果如下所示，成功的解決了文章前言中所講的問題。

完整代碼請(qǐng)移步：GetLinkedListNode-test.ts。

注意：上述代碼中用到的LinkedList是自定義的一個(gè)類，它實(shí)現(xiàn)了鏈表這個(gè)數(shù)據(jù)結(jié)構(gòu)。

示例代碼

本文所列舉的代碼，其完整版請(qǐng)移步：

• GetLinkedListNode.ts
• GetLinkedListNode-test.ts