class Node(object):
? ? def __init__(self, elem, next_=None):
? ? ? ? self.elem = elem
? ? ? ? self.next = next_
?
def reverseList(head):
? ? if head == None or head.next==None: ?# 若鏈表為空或者僅一個(gè)數(shù)就直接返回
? ? ? ? return head?
? ? pre = None
? ? next = None
? ? while(head != None):?
? ? ? ? next = head.next ? ? # 1
? ? ? ? head.next = pre ? ? # 2
? ? ? ? pre = head ? ? ?# 3
? ? ? ? head = next ? ? ?# 4
? ? return pre

if __name__ == '__main__':
? ? l1 = Node(3) ? ?# 建立鏈表3->2->1->9->None
? ? l1.next = Node(2)
? ? l1.next.next = Node(1)
? ? l1.next.next.next = Node(9)
? ? l = reverseList(l1)
? ? print (l.elem, l.next.elem, l.next.next.elem, l.next.next.next.elem)

原始單鏈表：

反轉(zhuǎn)后單鏈表：

反轉(zhuǎn)過程如下：

第一步：next = head.next
將 head.next 賦值給 next 變量，即next 指向了節(jié)點(diǎn)2，先將節(jié)點(diǎn)2 保存起來。

第二步：head.next = pre （初始pre==None）
將 pre 變量賦值給 head.next，即此時(shí)節(jié)點(diǎn)1 指向了 None

第三步：pre = head
將 head 賦值給了 pre，即 pre 指向節(jié)點(diǎn)1，將節(jié)點(diǎn)1 設(shè)為“上一個(gè)節(jié)點(diǎn)”

第四步：head = next
將 next 賦值給 head，即 head 指向了節(jié)點(diǎn)2，此時(shí)節(jié)點(diǎn)2 設(shè)為“頭節(jié)點(diǎn)”

第一次循環(huán)完畢，進(jìn)入第二次循環(huán)，如下圖：

第一步：next = head.next
將 head.next 賦值給 next 變量，即 next 指向了節(jié)點(diǎn)3，先將節(jié)點(diǎn)3 保存起來。

第二步：head.next = pre （此時(shí)的pre已經(jīng)不為None）
將 pre 賦值給 head.next，pre 在上一次循環(huán)的時(shí)候指向了節(jié)點(diǎn)1，那么這一步的意義就是節(jié)點(diǎn)2 指向了節(jié)點(diǎn)1，完成1和2節(jié)點(diǎn)的反轉(zhuǎn)。

第三步：pre = head
將 head 賦值給了 pre，即 pre 指向節(jié)點(diǎn)2，將節(jié)點(diǎn)2 設(shè)為“上一個(gè)節(jié)點(diǎn)”

第四步：head = next
將 next 賦值給 head，即 head 指向了節(jié)點(diǎn)3。此時(shí)節(jié)點(diǎn)3 設(shè)為“頭節(jié)點(diǎn)”

第二次循環(huán)完畢，以此類推！第三次第四次第五次循環(huán)。最后反轉(zhuǎn)成如下圖