數據結構與算法-反轉單鏈表
大家好，歡迎回到我們的算法學習系列。今天，我們將探討一個在算法面試中非常經典的問題——反轉單鏈表。
什么是單鏈表？
在介紹問題之前，我們先簡單了解一下單鏈表。單鏈表是一種線性數據結構，由一系列節點組成，每個節點包含兩個部分：存儲數據的部分和指向下一個節點的指針。鏈表的第一個節點稱為頭節點，最后一個節點的指針指向 null，表示鏈表的結束。
反轉單鏈表問題描述
給定一個單鏈表的頭節點，反轉這個鏈表，使得鏈表的尾節點變為頭節點，并返回新的頭節點。
示例
- 輸入：
1 -> 2 -> 3 -> 4 -> 5 -> null - 輸出：
5 -> 4 -> 3 -> 2 -> 1 -> null
解決思路
我們可以通過迭代的方法來反轉單鏈表。基本思路是遍歷鏈表，并將當前節點的指針指向前一個節點，從而改變鏈表的方向。
實現代碼
下面是用JavaScript實現這個算法的代碼：
function ListNode(val) {this.val = val;this.next = null;
}function reverseList(head) {let prev = null;let curr = head;while (curr !== null) {let nextTemp = curr.next;curr.next = prev;prev = curr;curr = nextTemp;}return prev;
}
代碼解析
- 定義節點結構：
ListNode是一個鏈表節點的構造函數，每個節點有一個值val和一個指向下一個節點的指針next。 - 初始化指針：我們定義兩個指針
prev和curr，分別表示前一個節點和當前節點。初始時，prev為null，curr為頭節點head。 - 遍歷鏈表：
- 保存下一個節點：我們用
nextTemp保存當前節點的下一個節點。 - 反轉指針：將當前節點的指針指向前一個節點。
- 移動指針：更新
prev和curr指針，進入下一個節點。
- 保存下一個節點：我們用
- 返回新的頭節點：遍歷結束后，
prev指向反轉后的新頭節點，返回prev。
圖解
讓我們通過圖解來理解反轉過程：
初始鏈表：
head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
prev curr
第一步：
head -> 1 -> null
prev curr
第二步：
head -> 2 -> 1 -> null
prev curr
第三步：
head -> 3 -> 2 -> 1 -> null
prev curr
依次類推，直到 curr 為 null，鏈表反轉完成。
小結
今天，我們介紹了反轉單鏈表的問題及其解決方法。通過迭代的方法，我們可以高效地反轉一個單鏈表，這是一個在面試中經常遇到的經典問題。
感謝大家的閱讀！如果你有任何問題或建議，歡迎在評論區留言。
