題目
難度：★★☆☆☆
類(lèi)型：鏈表
反轉(zhuǎn)一個(gè)單鏈表。
進(jìn)階:
你可以迭代或遞歸地反轉(zhuǎn)鏈表。你能否用兩種方法解決這道題？
示例
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
解答
方案1：迭代
使用迭代法反轉(zhuǎn)鏈表需要三個(gè)臨時(shí)變量：
當(dāng)前結(jié)點(diǎn)cur：當(dāng)前要處理的鏈表結(jié)點(diǎn)；
前一個(gè)結(jié)點(diǎn)prev：已經(jīng)處理好的新鏈表的頭結(jié)點(diǎn)；
臨時(shí)結(jié)點(diǎn)tmp：用于暫存cur的下一個(gè)鏈表結(jié)點(diǎn)。
遍歷鏈表過(guò)程中，不斷進(jìn)行的重復(fù)便是cur.next=prev：
prev, cur->tmp ==> prev <- cur, tmp
每一輪循環(huán)，因?yàn)橛腥齻€(gè)變量，所以需要三句話(huà)分別更新，鏈表方向調(diào)頭工序夾在里面：
先把當(dāng)前結(jié)點(diǎn)cur的下一個(gè)結(jié)點(diǎn)賦給臨時(shí)結(jié)點(diǎn)tmp暫存；
將當(dāng)前結(jié)點(diǎn)的連接方向調(diào)頭，連接prev，cur成為新鏈表的頭結(jié)點(diǎn)；
prev結(jié)點(diǎn)更新為新鏈表的頭結(jié)點(diǎn)；
將tmp中暫存的變量歸還cur結(jié)點(diǎn)。
class Solution(object): # 迭代
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
cur, prev = head, None
while cur:
tmp = cur.next # 臨時(shí)列表，用于暫存結(jié)果
cur.next = prev # 更換連接方向
prev = cur # 后移
cur = tmp # 后移
return prev
方案2：遞歸
假設(shè)鏈表為：
1 -> 2 -> 3-> ... -> k-1 -> k -> k+1 -> ... -> n -> None
并且我們已經(jīng)構(gòu)造了函數(shù)，使得鏈表從k-1之后都被反轉(zhuǎn)：
1 -> 2 -> 3-> ... ->k-1 -> k -> k+1 <- ... <- n
我們希望k-1的下一個(gè)結(jié)點(diǎn)指向k，則k.next.next=k：
1 -> 2 -> 3-> ... ->k-1 -> k <- k+1 <- ... <- n
需要注意的是，結(jié)點(diǎn)1的下一個(gè)結(jié)點(diǎn)是None，需要特殊處理，在之前操作的基礎(chǔ)上設(shè)置k的下一個(gè)結(jié)點(diǎn)為None：
n -> n-1 -> ... -> k+1 \
??????????-> k -> None
1-> 2-> 3 -> ... ->k-1 /
class Solution(object): # 迭代
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next: # 如果輸入結(jié)點(diǎn)是空，或只有一個(gè)結(jié)點(diǎn)，返回即可
return head
p = self.reverseList(head.next) # 將下一個(gè)結(jié)點(diǎn)之后的部分逆序
head.next.next = head # 反轉(zhuǎn)當(dāng)前結(jié)點(diǎn)
head.next = None # 設(shè)置當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)為None
return p
這里，特地為大家做了一個(gè)腳本，近距離展示一下遞歸是如何工作的：
def create_linked_list(nums):
"""
創(chuàng)建鏈表
:param nums: 輸入代表里鏈表的數(shù)字列表
:return: 返回創(chuàng)建好的鏈表的頭結(jié)點(diǎn)，可以得到整個(gè)鏈表的所有信息
"""
if not nums: # 輸入空列表
return
head = prev = ListNode(nums[0]) # 第一個(gè)結(jié)點(diǎn)
for num in nums[1:]:
tmp = ListNode(num) # 創(chuàng)建當(dāng)前結(jié)點(diǎn)
prev.next = tmp # 掛在已經(jīng)創(chuàng)建好的鏈表末尾
prev = prev.next # 指針后移
return head
def print_linked_list(head):
"""
打印鏈表
:param head: 要打印的鏈表的頭結(jié)點(diǎn)
:return: 結(jié)點(diǎn)值列表
"""
nums = []
while head:
nums.append(head.val)
head = head.next
print(nums)
return nums
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next: # 如果輸入結(jié)點(diǎn)是空，或只有一個(gè)結(jié)點(diǎn)，返回即可
return head
p = self.reverseList(head.next) # 將下一個(gè)結(jié)點(diǎn)之后的部分逆序
head.next.next = head # 反轉(zhuǎn)當(dāng)前結(jié)點(diǎn)
head.next = None # 設(shè)置當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)為None
print_linked_list(p) # 展示一下處理過(guò)程，如果不需要的話(huà)可以注釋掉
return p
if __name__ == "__main__":
head = create_linked_list([1, 2, 3, 4, 5, 6, 7, 8, 9])
s = Solution()
reversed_head = s.reverseList(head)
該腳本的輸出為：
[9, 8]
[9, 8, 7]
[9, 8, 7, 6]
[9, 8, 7, 6, 5]
[9, 8, 7, 6, 5, 4]
[9, 8, 7, 6, 5, 4, 3]
[9, 8, 7, 6, 5, 4, 3, 2]
[9, 8, 7, 6, 5, 4, 3, 2, 1]
創(chuàng)建鏈表（create_linked_list）和打印鏈表（print_linked_list）函數(shù)源自【鏈表基礎(chǔ)】。
如有疑問(wèn)或建議，歡迎評(píng)論區(qū)留言~
