反轉(zhuǎn)一個(gè)單鏈表。
示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
- show the code:
# Definition for singly-linked list.
# 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
"""
reversehead = None
p = head
p_pre = None
while p:
p_next = p.next
if not p_next:
reversehead = p
p.next = p_pre
p_pre = p
p = p_next
return reversehead
- 此題屬于經(jīng)典題，之前做過(guò)很多次了，拿到之后還是無(wú)從下手。。。劍指offer上講的很詳細(xì)，關(guān)鍵是考慮清楚三個(gè)節(jié)點(diǎn)的情況，其中現(xiàn)有遍歷的節(jié)點(diǎn)指針指向其之前的節(jié)點(diǎn)，這里特別注意，為了防止鏈表斷開(kāi)，我們需要事先保存好現(xiàn)在節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，所以總的來(lái)說(shuō)會(huì)有四個(gè)變量：
reversehead反轉(zhuǎn)后的頭節(jié)點(diǎn)，p現(xiàn)有遍歷到的節(jié)點(diǎn)，p_pre現(xiàn)有節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)，p_next現(xiàn)有節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) - 理清這個(gè)情況之后就簡(jiǎn)單了，接下來(lái)需要判斷循環(huán)終止條件?？紤]到反轉(zhuǎn)后的鏈表頭節(jié)點(diǎn)是反轉(zhuǎn)前鏈表的尾節(jié)點(diǎn)，所以當(dāng)
p_next是None時(shí)說(shuō)明鏈表遍歷結(jié)束，反轉(zhuǎn)結(jié)束。
