實現鏈表反轉

語言: CN / TW / HK

前言

有一個鏈表,如何將其反轉並獲取反轉後的鏈表頭節點?本文將分享一種解決方案,歡迎各位感興趣的開發者閲讀本文。

思路分析

經過數據結構基礎的學習,我們知道鏈表中每個節點都會有一個指針,用於指向它的下一個節點,那麼,我們只需要從鏈表頭部開始遍歷,逐一修改它的指針指向至其上一個節點,即可完成鏈表的反轉。

這個思路的難點在於如何調整指針的指向,我們可以藉助3個指針來完成這個操作,如下所示:

  • p1、p3分別是p2指針的上、下一個節點(默認指向null)
  • 如果p2指針指向的節點不為null
  • 獲取p2指針指向的下一個節點,將其保存至p3
  • 如果p3的值為null,則表示鏈表已經反轉完畢,用一個變量存儲p2的值
  • 修改p2指針的指向至p1,修改p1的值為p2,修改p2的值為p3

IMG_12BA2C91C60A-1

實現代碼

通過上面的分析,我們分析出了可以用三指針來解決問題的思路,接下來,我們來看下代碼實現。

首先,設計一個名為ReverseLinkedList的類:

  • 內部有2個私有變量

  • pPrev p1指針

  • pNode p2指針
  • 構造方法接受1個參數:鏈表頭節點
  • 對參數進行校驗
  • 初始化p2指針指向為鏈表頭節點,p1指針的指向為null

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

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

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

緊接着,實現鏈表反轉函數:

  • 聲明一個變量用於存儲反轉後的鏈表頭指針
  • 移動p2指針,開始遍歷鏈表
  • 存儲p2指針的下一個節點至p3
  • 判斷p2指針是否為走到鏈表末尾,條件成立就修改存儲p2節點至反轉後的鏈表頭指針變量
  • 修改p2指針的指向至p1,修改p1的值為p2,修改p2的值為p3
  • p2指針指向null,返回得到的鏈表頭節點

typescript reverseList(): ListNode | null { // 反轉後的鏈表頭指針 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; }

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

測試用例

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

```typescript 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("反轉後的鏈表頭節點為", result);

```

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

image-20220615221918607

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

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

示例代碼

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

寫在最後

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

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

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

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