題目描述
輸入一個復(fù)雜鏈表（每個節(jié)點中有節(jié)點值只磷，以及兩個指針，一個指向下一個節(jié)點射众，另一個特殊指針指向任意一個節(jié)點），返回結(jié)果為復(fù)制后復(fù)雜鏈表的head晃财。（注意叨橱，輸出結(jié)果中請不要返回參數(shù)中的節(jié)點引用，否則判題程序會直接返回空）
知識點
鏈表
Qiang的思路
這道題提出了一種復(fù)雜鏈表断盛，然后定義它的復(fù)制操作罗洗。如果是一個普通的鏈表，值需要對每個節(jié)點復(fù)制钢猛，然后遵循之前的指向連接起來就可以了伙菜，但是對于這個復(fù)雜鏈表，僅僅這樣做是肯定無法實現(xiàn)對其復(fù)制的命迈。但是思路是一樣的贩绕。
針對next指針，我們可以按照普通鏈表復(fù)制的方式壶愤，一個節(jié)點一個節(jié)點的復(fù)制淑倾，并將指向也復(fù)制過來。這樣就可以得到一個沒有random指向的復(fù)雜鏈表征椒。
接下來就是要將random指針的指向還原娇哆。想要還原這個指針，我們必須要知道一個指針指向的節(jié)點對應(yīng)在鏈表中的位置，然后根據(jù)這個問題去找到新鏈表中的節(jié)點迂尝，然后然后random指針的復(fù)制脱茉。
對于這個位置問題，我們可以理解為找到一個節(jié)點和其在鏈表中位置的對應(yīng)關(guān)系垄开，所以也就想到了用字典去實現(xiàn)這個功能琴许。
于是定義了一個字典，鍵就是節(jié)點溉躲，值就是節(jié)點在鏈表中的位置榜田。然后便可以知道random指向的節(jié)點在鏈表中的位置了。為了不用每次遍歷鏈表尋找該位置的節(jié)點锻梳，我們使用了一個list存儲所有的節(jié)點箭券，并保持去位置順序不變。這樣就可以根據(jù)位置在常數(shù)級的時間內(nèi)找到節(jié)點疑枯，然后完成random指針的復(fù)制操作辩块。
# -*- coding:utf-8 -*-
# class RandomListNode:
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
# write code here
if pHead==None:
return None
l=[]
d={}
result=RandomListNode(pHead.label)
l.append(result)
pre=result
root=pHead.next
d[pHead]=0
count=1
while root!=None:
pre.next=RandomListNode(root.label)
pre=pre.next
d[root]=count
root=root.next
count+=1
l.append(pre)
count=0
while pHead!=None:
if pHead.random!=None:
l[count].random=l[d[pHead.random]]
pHead=pHead.next
count+=1
return result
這道題也是一直卡著沒過，一開始的時候倒數(shù)第4,5行沒有判斷荆永，也就是沒有倒數(shù)第5行废亭，但是這就會有一個問題，因為鏈表中的next指針除了尾節(jié)點其余的節(jié)點都是有的具钥，但是random指針每個節(jié)點都有可能沒有豆村，所以直接使用這個指針作為鍵去索引對應(yīng)的值是有問題的。最后通過一個判斷解決了該問題骂删。
Book中的思路
書中給出了一種思路掌动，可以在不適用輔助空間的基礎(chǔ)上完成該功能。
具體是在進行節(jié)點復(fù)制時將每一個節(jié)點復(fù)制的節(jié)點放到該節(jié)點的后面宁玫，當(dāng)完成一遍節(jié)點復(fù)制之后相當(dāng)于將原來的鏈表變?yōu)樵瓉淼囊槐洞只郑總€節(jié)點在相鄰的位置重復(fù)出現(xiàn)。這樣在進行random指針的復(fù)制時只需要按照原節(jié)點的random指向撬统，將當(dāng)前節(jié)點的random指向原節(jié)點random指針的下一個節(jié)點即可适滓。
但是在編程時還是遇到了問題，下面是錯誤的程序恋追。
# -*- coding:utf-8 -*-
# class RandomListNode:
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
# write code here
if pHead==None:
return None
root=pHead
while root!=None:
node=RandomListNode(root.label)
node.next=root.next
root.next=node
root=root.next.next
result=RandomListNode(None)
pre=result
root=pHead
while root!=None:
pre.next=root.next
pre=pre.next
if root.random!=None:
pre.random=root.random.next
root=root.next.next
return result.next
錯誤描述：空凭迹。請檢查一下你的代碼，有沒有循環(huán)輸入處理多個case苦囱。點擊查看如何處理多個case
目前還目前解決嗅绸，先放一下，回頭再看看撕彤。
作者原創(chuàng)鱼鸠，如需轉(zhuǎn)載及其他問題請郵箱聯(lián)系：lwqiang_chn@163.com猛拴。
個人網(wǎng)站：https://www.myqiang.top。
