前言

以專題的形式更新刷題貼，歡迎跟我一起學習刷題，相信我，你的堅持，絕對會有意想不到的收獲。每道題會提供簡單的解答，如果你有更優雅的做法，歡迎提供指點，謝謝

【題目描述】

反轉單鏈表。例如鏈表為：

1->2->3->4

反轉后為

4->3->2->1

【要求】

如果鏈表的長度為 N, 時間復雜度達到 O(N), 額外空間復雜度達到 O(1)

【難度】

士：★☆☆☆

【解答】

方法1

這道題還是挺簡單的，當我們在反轉一個節點的時候，把一個節點的后驅改為指向它前驅就可以了。這里需要注意的點就是，當你把當前節點的后驅指向前驅的時候，這個時候鏈表會被截斷，也就是說后面的節點和當前節點分開了，所以我們需要一個變量來保存當前節點的后驅，以訪丟失。

具體代碼如下：

代碼如下

方法二

這道題也可以用遞歸來做，假設 方法 reverse() 的功能是將單鏈表進行逆轉。采用遞歸的方法時，我們可以不斷著對子鏈表進行遞歸。例如對于如下的鏈表：

我們對子鏈表 2->3->4 進行遞歸，即

Node newList = reverse(head.next)。遞歸之后的結果如下：

逆轉之后子鏈表 2->3->變為了 4->3->2。

注意，我剛才假設 reverse() 的功能就是對鏈表進行逆轉。不過此時節點 1 仍然是指向節點 2 的。這個時候，我們再把節點1 和 2逆轉一下，然后 1 的下一個節點指向 null 就可以了。如圖：

遞歸的結束條件就是：當子鏈表只有一個節點，或者為 null 時，遞歸結束。代碼如下：

問題拓展

題目：反轉部分鏈表節點

【題目描述】

題目：給定一個單向鏈表的頭結點head,以及兩個整數from和to ,在單項鏈表上把第from個節點和第to個節點這一部分進行反轉

列如：

1->2->3->4->5->null,from=2,to=4

結果：1->4->3->2->5->null

列如：

1->2->3->null from=1,to=3

結果為3->2->1->null

【要求】

1、如果鏈表長度為N，時間復雜度要求為O(N),額外空間復雜度要求為O(1)

2、如果不滿足1<=from<=to<=N,則不調整

【難度】

士：★☆☆☆

【解答】

每日推送原創文章，專注于寫數據結構與算法，輔寫計算機網絡、計算機基礎、Java，期待各位的關注，保證讓你有所收獲。不信你試試

總結

以上是生活随笔為你收集整理的java 链表反转_剑指BAT：如何最优雅着反转单链表？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。