定義一個(gè)函數(shù)，輸入一個(gè)鏈表的頭節(jié)點(diǎn)，反轉(zhuǎn)該鏈表并輸出反轉(zhuǎn)后鏈表的頭節(jié)點(diǎn)。

示例

• 輸入: 1->2->3->4->5->NULL

• 輸出: 5->4->3->2->1->NULL

限制

• 0 <= 節(jié)點(diǎn)個(gè)數(shù) <= 5000

方法一：迭代（雙指針）

考慮遍歷鏈表，并在訪問各節(jié)點(diǎn)時(shí)修改 next 引用指向。

以示例為例：

• 初始化：pre→null，cur→1→2→3→4→5→null

• 臨時(shí)變量指向當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)指向null：temp→2→3→4→5->null，cur→1→null，

• pre 保存當(dāng)前節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)存儲(chǔ)臨時(shí)節(jié)點(diǎn)：cur→2→3→4→5->null ，pre→1→null，temp→2

• 當(dāng) 當(dāng)前節(jié)點(diǎn) 為空時(shí)，退出循環(huán)；

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度： O(N)，遍歷鏈表使用線性大小時(shí)間。

• 空間復(fù)雜度： O(1)，變量 pre 和 cur 使用常數(shù)大小的額外空間。

方法二：遞歸

考慮使用遞歸法遍歷鏈表，當(dāng)越過尾節(jié)點(diǎn)后終止遞歸，在回溯時(shí)修改各節(jié)點(diǎn)的 next 引用指向。

recur(cur, pre) 遞歸函數(shù)：

• 終止條件：當(dāng) cur 為空，則返回尾節(jié)點(diǎn) pre （即反轉(zhuǎn)鏈表的頭節(jié)點(diǎn)）；

• 遞歸后繼節(jié)點(diǎn)，記錄返回值（即反轉(zhuǎn)鏈表的頭節(jié)點(diǎn)）為 res ；

• 修改當(dāng)前節(jié)點(diǎn) cur 引用指向前驅(qū)節(jié)點(diǎn) pre ；

• 返回反轉(zhuǎn)鏈表的頭節(jié)點(diǎn) res ；

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度： O(N)，遍歷鏈表使用線性大小時(shí)間。

• 空間復(fù)雜度： O(N)，遍歷鏈表的遞歸深度達(dá)到 N ，系統(tǒng)使用 O(N) 大小額外空間。

END

本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強(qiáng)！

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號(hào)“javaAnswer”，全部都是干貨。