題目
給定一個(gè)帶頭節(jié)點(diǎn)的單鏈表:
head->1->2->3->4->5->6->7->8
使其成為:
head->8->7->6->5->4->3->2->1
就地逆序法(這是方法一范咨,后續(xù)會(huì)有其他方法)
python語言中并沒有指針和數(shù)組灼芭,因此用引用來實(shí)現(xiàn)
先定義一個(gè)節(jié)點(diǎn)對象——有數(shù)據(jù)和后續(xù)節(jié)點(diǎn)地址兩部分組成
class LNode:
def __init__(self, x):
self.data = x
self.next = None
def Reverse(head):
''' 有頭節(jié)點(diǎn)
:param head:
:return:
'''
# 判斷鏈表是否為空
if head is None or head.next is None:
return
pre = None
cur = None
next = None
# 處理鏈表頭
cur = head.next
next = cur.next
cur.next = None
pre = cur
cur = next
# 轉(zhuǎn)變當(dāng)前節(jié)點(diǎn)指向
while cur.next != None:
next = cur.next
cur.next = pre
pre = cur
cur = next
# 處理最后一個(gè)節(jié)點(diǎn)與倒數(shù)第二個(gè)節(jié)點(diǎn)
cur.next = pre
# 添加頭節(jié)點(diǎn)
head.next = cur
if __ name __ == '__main __':
i = 1
head = LNode(None)
# head.data=None
# head.next=None
cur = head
tmp = None # 用作添加新節(jié)點(diǎn)
# 構(gòu)造單鏈表
while i <= 8:
tmp = LNode(i)
# tmp.data=i
# tmp.next=None
cur.next = tmp
cur = tmp
i += 1
print("BeforeReverse:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
print("\nAfterReverse:")
Reverse(head)
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
輸出如下:(我用的pycharm)
寫在最后:
我對Markdown語法還不太熟悉雄家,不太明白怎么把代碼正確的顯示出來昭伸。例如上面的if __ name __ == "__ main __" 我不能使它成為代碼的一部分,這讓我很頭疼离陶。請大家教教我謝謝稼虎。
本文代碼在我的Github上有“https://github.com/Gesujian/python-”如發(fā)現(xiàn)錯(cuò)誤請指正,謝謝^ _^