建站
咨詢
售后
建站咨詢
新聞中心
前言
思路分析
經(jīng)過數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)的學(xué)習(xí)，我們知道鏈表中每個節(jié)點都會有一個指針，用于指向它的下一個節(jié)點，那么，我們只需要從鏈表頭部開始遍歷，逐一修改它的指針指向至其上一個節(jié)點，即可完成鏈表的反轉(zhuǎn)。
站在用戶的角度思考問題，與客戶深入溝通，找到都蘭網(wǎng)站設(shè)計與都蘭網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗，讓設(shè)計與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個性化、用戶體驗好的作品，建站類型包括：網(wǎng)站制作、做網(wǎng)站、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、域名注冊、網(wǎng)絡(luò)空間、企業(yè)郵箱。業(yè)務(wù)覆蓋都蘭地區(qū)。
這個思路的難點在于如何調(diào)整指針的指向，我們可以借助3個指針來完成這個操作，如下所示：
- p1、p3分別是p2指針的上、下一個節(jié)點（默認(rèn)指向null）
- 如果p2指針指向的節(jié)點不為null
獲取p2指針指向的下一個節(jié)點，將其保存至p3
如果p3的值為null，則表示鏈表已經(jīng)反轉(zhuǎn)完畢，用一個變量存儲p2的值
修改p2指針的指向至p1，修改p1的值為p2，修改p2的值為p3
實現(xiàn)代碼
通過上面的分析，我們分析出了可以用三指針來解決問題的思路，接下來，我們來看下代碼實現(xiàn)。
首先，設(shè)計一個名為ReverseLinkedList的類：
- 內(nèi)部有2個私有變量。
pPrev p1指針
pNode p2指針
- 構(gòu)造方法接受1個參數(shù)：鏈表頭節(jié)點。
對參數(shù)進(jìn)行校驗。
初始化p2指針指向為鏈表頭節(jié)點，p1指針的指向為null。
export class ReverseLinkedList {
// p1指針
private pPrev: ListNode | null;
// p2指針
private pNode: ListNode | null;
constructor(listHead: ListNode) {
if (listHead == null) {
throw new Error("鏈表頭節(jié)點不能為空");
}
this.pNode = listHead;
this.pPrev = null;
}
}上述代碼中，我們用了一個自定義類型ListNode，它描述了一個鏈表的節(jié)點應(yīng)該包含哪些屬性，對此感興趣的開發(fā)者請移步我的另一篇文章：鏈表與變相鏈表的實現(xiàn)。
緊接著，實現(xiàn)鏈表反轉(zhuǎn)函數(shù)：
- 聲明一個變量用于存儲反轉(zhuǎn)后的鏈表頭指針。
- 移動p2指針，開始遍歷鏈表。
存儲p2指針的下一個節(jié)點至p3。
判斷p2指針是否為走到鏈表末尾，條件成立就修改存儲p2節(jié)點至反轉(zhuǎn)后的鏈表頭指針變量。
修改p2指針的指向至p1，修改p1的值為p2，修改p2的值為p3。
- p2指針指向null，返回得到的鏈表頭節(jié)點。
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;
}完整代碼請移步：ReverseLinkedList.ts
測試用例
接下來，我們將前言中的例子代入上個章節(jié)所實現(xiàn)的函數(shù)中，驗證下它能否得出正確的結(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é)點為", result);
運行結(jié)果如下所示，成功的解決了文章前言中所講的問題。
完整代碼請移步：reverseLinkedList-test.ts
示例代碼：
本文所列舉的代碼，其完整版請移步：
- ReverseLinkedList.ts
- reverseLinkedList-test.ts
網(wǎng)站題目：實現(xiàn)鏈表反轉(zhuǎn)，你學(xué)會了嗎？
轉(zhuǎn)載來于：http://m.5511xx.com/article/cdiissp.html
