本文實(shí)例為大家分享了python實(shí)現(xiàn)單鏈表反轉(zhuǎn)的具體代碼，供大家參考，具體內(nèi)容如下

代碼如下：

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)成如下圖

若干注意點(diǎn)：

(1)幫助記憶圖：

(2)當(dāng)前頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)一定要保存（比如：當(dāng)前頭節(jié)點(diǎn)為2，先將節(jié)點(diǎn)3 保存起來）

(3)實(shí)現(xiàn)反轉(zhuǎn)的key point: head.next = pre

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論