我一生最大的功勞，就是保住了錢鐘書的淘氣和那一團(tuán)癡氣，讓錢鐘書的天性沒(méi)有受到壓迫，沒(méi)有受到損傷?！獥罱{
真好！
今天電腦出問(wèn)題了，現(xiàn)在在一個(gè)安裝在U盤中的ubuntu里，寫這個(gè)文章，時(shí)間倉(cāng)促，見(jiàn)諒！
題目：題目：給定一個(gè)無(wú)序鏈表，例如：head->1->2>1-->3->3->5->7->6>7->8,刪除其中的重復(fù)項(xiàng)，將其變成head->1->2->5->7->6->8。
昨天介紹的利用HashSet集合，成功的解決了上面的問(wèn)題，而且時(shí)間復(fù)雜度降到了O(N)，因?yàn)檫@種方法只需要遍歷一次。之前我們也用了順序刪除的方法，也完成了題目的要求。那么之前將講過(guò)的遞歸是否能解決這個(gè)問(wèn)題呢？下面我們一起來(lái)看一下：
解決這個(gè)問(wèn)題主要分為兩個(gè)主要步驟：1）判斷當(dāng)前節(jié)點(diǎn)是否重復(fù)出現(xiàn)過(guò)；2）刪除節(jié)點(diǎn)。至于刪除節(jié)點(diǎn)前面講過(guò)了——刪除節(jié)點(diǎn)。順序刪除法是通過(guò)內(nèi)外兩層循環(huán)，判斷內(nèi)循環(huán)是否存在外循環(huán)遍歷的節(jié)點(diǎn)；HashSet法是利用了python集合的特性。遞歸程序的兩個(gè)要素之前強(qiáng)調(diào)過(guò)了——遞歸定義與遞歸終止條件。主要思路為：遍歷鏈表，并刪除其子鏈表中與當(dāng)前節(jié)點(diǎn)cur數(shù)據(jù)域相同的節(jié)點(diǎn)，然后刪除cur.next的子鏈表中與其數(shù)據(jù)域相同的節(jié)點(diǎn)。
下面是算法代碼：
"""
題目描述：
將Head->1->1->3->3->5->7->7->8變
為head->1->2->5->7->8
方法：遞歸法2
"""
def RemoveDup(head):
if head.next is None:
return head
#這里的if語(yǔ)句只是為了判斷遞歸是否到了最后第二個(gè)節(jié)點(diǎn)，所以下面不需要else語(yǔ)句
#直接寫在if同一層就行。
pre=head#
cur=head.next
head.next=RemoveDup(head.next)
# 注意是head.next 因?yàn)檫@里是去掉與head相同的值，但是head還是留下來(lái)的
while cur is not None:
if cur.data == head.data:
pre.next=cur.next
cur=cur.next
#刪除重復(fù)節(jié)點(diǎn)的操作：
# ___________________________
# / \
# | V
# 1 -----> 1 -----> 2
# ^ ^
# | |
# pre cur
# 這不知道你們能不能看懂。。。。
else:
#遍歷下一個(gè)節(jié)點(diǎn)
cur=cur.next
pre=pre.next
return head
構(gòu)造無(wú)序鏈表：
#先引入random庫(kù)
import random
#依然是先定義節(jié)點(diǎn)類
class LNode(object):
def __init__(self, arg):
self.data = arg
self.next = None
#這里!前幾篇的create我寫錯(cuò)了，少了個(gè)e,
#這里改用construct 構(gòu)造的意思
def construstLink(x):
i = 1
head = LNode(None)
tmp = None
cur = head
while i <= x:
#這里與之前不同，先生成一個(gè)隨機(jī)數(shù)，作為節(jié)點(diǎn)值
n = random.randint(0, 9)
tmp = LNode(n)
cur.next = tmp
cur = tmp
i += 1
return head
主程序：
if __name__ == '__main__':
#構(gòu)造鏈表
head=construstLink(10)
#打印處理之前的鏈表
print("BeforeReverse:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
#調(diào)用算法，處理鏈表
head = RemoveDup(head)
# 打印處理之后的鏈表
print("\nAfterReverse:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
運(yùn)行結(jié)果(linux)：
全部代碼：
#先引入random庫(kù)
import random
#依然是先定義節(jié)點(diǎn)類
class LNode(object):
def __init__(self, arg):
self.data = arg
self.next = None
#這里!前幾篇的create我寫錯(cuò)了，少了個(gè)e,
#這里改用construct 構(gòu)造的意思
def construstLink(x):
i = 1
head = LNode(None)
tmp = None
cur = head
while i <= x:
#這里與之前不同，先生成一個(gè)隨機(jī)數(shù)，作為節(jié)點(diǎn)值
n = random.randint(0, 9)
tmp = LNode(n)
cur.next = tmp
cur = tmp
i += 1
return head
"""
題目描述：
將Head->1->1->3->3->5->7->7->8變
為head->1->2->5->7->8
方法：遞歸法2
"""
def RemoveDup(head):
if head.next is None:
return head
#這里的if語(yǔ)句只是為了判斷遞歸是否到了最后第二個(gè)節(jié)點(diǎn)，所以下面不需要else語(yǔ)句
#直接寫在if同一層就行。
pre=head#
cur=head.next
head.next=RemoveDup(head.next)
# 注意是head.next 因?yàn)檫@里是去掉與head相同的值，但是head還是留下來(lái)的
while cur is not None:
if cur.data == head.data:
pre.next=cur.next
cur=cur.next
#刪除重復(fù)節(jié)點(diǎn)的操作：
# pre cur
# | |
# |______|______
# \ >
# \ /
# \_________/這不知道你們能不能看懂。。。。
#這里在微信顯示不太正常，網(wǎng)頁(yè)，app內(nèi)是正常的
else:
#遍歷下一個(gè)節(jié)點(diǎn)
cur=cur.next
pre=pre.next
return head
if __name__ == '__main__':
#構(gòu)造鏈表
head=construstLink(10)
#打印處理之前的鏈表
print("BeforeReverse:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
#調(diào)用算法，處理鏈表
head = RemoveDup(head)
# 打印處理之后的鏈表
print("\nAfterReverse:")
cur = head.next
while cur != None:
print(cur.data)
cur = cur.next
好的，今天的算法就到這，因?yàn)殡娔X原因，原來(lái)準(zhǔn)備好的程序暫時(shí)沒(méi)找到，現(xiàn)寫的會(huì)出問(wèn)題（老師講的）而且注釋并不太全，不過(guò)我也盡力寫上了。還有，這個(gè)老師還說(shuō)：程序算法最好用流程圖表示出來(lái)，寫程序前寫程序后都要，這是一個(gè)好習(xí)慣，可以讓大家更好的理解算法。所以過(guò)幾天，會(huì)開(kāi)始在分析算法時(shí)將流程圖貼出來(lái)，讓我們更好的理解。當(dāng)然這一切都得等我電腦弄好了。（linux真好看）
是個(gè)狠人！
整個(gè)清華沒(méi)有一個(gè)教授有資格充當(dāng)錢某人的導(dǎo)師！——錢鐘書說(shuō)于清華大學(xué)
人謂我狂，不知我實(shí)狷?！X鐘書
