前言

有一個(gè)鏈表，如何將其反轉(zhuǎn)并獲取反轉(zhuǎn)后的鏈表頭節(jié)點(diǎn)？本文將分享一種解決方案，歡迎各位感興趣的開發(fā)者閱讀本文。

思路分析

經(jīng)過數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)的學(xué)習(xí)，我們知道鏈表中每個(gè)節(jié)點(diǎn)都會(huì)有一個(gè)指針，用于指向它的下一個(gè)節(jié)點(diǎn)，那么，我們只需要從鏈表頭部開始遍歷，逐一修改它的指針指向至其上一個(gè)節(jié)點(diǎn)，即可完成鏈表的反轉(zhuǎn)。

這個(gè)思路的難點(diǎn)在于如何調(diào)整指針的指向，我們可以借助3個(gè)指針來完成這個(gè)操作，如下所示：

• p1、p3分別是p2指針的上、下一個(gè)節(jié)點(diǎn)（默認(rèn)指向null）
• 如果p2指針指向的節(jié)點(diǎn)不為null

獲取p2指針指向的下一個(gè)節(jié)點(diǎn)，將其保存至p3

如果p3的值為null，則表示鏈表已經(jīng)反轉(zhuǎn)完畢，用一個(gè)變量存儲(chǔ)p2的值

修改p2指針的指向至p1，修改p1的值為p2，修改p2的值為p3

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

通過上面的分析，我們分析出了可以用三指針來解決問題的思路，接下來，我們來看下代碼實(shí)現(xiàn)。

首先，設(shè)計(jì)一個(gè)名為ReverseLinkedList的類：

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

pPrev p1指針

pNode p2指針

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

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

初始化p2指針指向?yàn)殒湵眍^節(jié)點(diǎn)，p1指針的指向?yàn)閚ull。

export class ReverseLinkedList {
  // p1指針
  private pPrev: ListNode | null;
  // p2指針
  private pNode: ListNode | null;

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

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

緊接著，實(shí)現(xiàn)鏈表反轉(zhuǎn)函數(shù)：

• 聲明一個(gè)變量用于存儲(chǔ)反轉(zhuǎn)后的鏈表頭指針。
• 移動(dòng)p2指針，開始遍歷鏈表。

存儲(chǔ)p2指針的下一個(gè)節(jié)點(diǎn)至p3。

判斷p2指針是否為走到鏈表末尾，條件成立就修改存儲(chǔ)p2節(jié)點(diǎn)至反轉(zhuǎn)后的鏈表頭指針變量。

修改p2指針的指向至p1，修改p1的值為p2，修改p2的值為p3。

• p2指針指向null，返回得到的鏈表頭節(jié)點(diǎn)。

  reverseList(): ListNode | null {
    // 反轉(zhuǎn)后的鏈表頭指針
    let pReversedHead: ListNode | null = null;
    while (this.pNode != null) {
      // p3指針
      const pNext = this.pNode.next;
      if (pNext == null) {
        pReversedHead = this.pNode;
      }
      this.pNode.next = this.pPrev;
      this.pPrev = this.pNode;
      this.pNode = pNext;
    }
    return pReversedHead;
  }

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

測(cè)試用例

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

const linkedList = new LinkedList();
linkedList.push(1);
linkedList.push(3);
linkedList.push(8);
linkedList.push(9);
linkedList.push(12);
linkedList.push(18);
const reverseLinkedList = new ReverseLinkedList(linkedList.getHead());
const result = reverseLinkedList.reverseList();
console.log("反轉(zhuǎn)后的鏈表頭節(jié)點(diǎn)為", result);

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

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

示例代碼：

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

• ReverseLinkedList.ts
• reverseLinkedList-test.ts