題目描述

輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值，以及兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)，另一個(gè)特殊指針指向任意一個(gè)節(jié)點(diǎn)），返回結(jié)果為復(fù)制后復(fù)雜鏈表的head。（注意，輸出結(jié)果中請(qǐng)不要返回參數(shù)中的節(jié)點(diǎn)引用，否則判題程序會(huì)直接返回空）

知識(shí)點(diǎn)

鏈表

Qiang的思路

這道題提出了一種復(fù)雜鏈表，然后定義它的復(fù)制操作。如果是一個(gè)普通的鏈表，值需要對(duì)每個(gè)節(jié)點(diǎn)復(fù)制，然后遵循之前的指向連接起來就可以了，但是對(duì)于這個(gè)復(fù)雜鏈表，僅僅這樣做是肯定無法實(shí)現(xiàn)對(duì)其復(fù)制的。但是思路是一樣的。

針對(duì)next指針，我們可以按照普通鏈表復(fù)制的方式，一個(gè)節(jié)點(diǎn)一個(gè)節(jié)點(diǎn)的復(fù)制，并將指向也復(fù)制過來。這樣就可以得到一個(gè)沒有random指向的復(fù)雜鏈表。

接下來就是要將random指針的指向還原。想要還原這個(gè)指針，我們必須要知道一個(gè)指針指向的節(jié)點(diǎn)對(duì)應(yīng)在鏈表中的位置，然后根據(jù)這個(gè)問題去找到新鏈表中的節(jié)點(diǎn)，然后然后random指針的復(fù)制。

對(duì)于這個(gè)位置問題，我們可以理解為找到一個(gè)節(jié)點(diǎn)和其在鏈表中位置的對(duì)應(yīng)關(guān)系，所以也就想到了用字典去實(shí)現(xiàn)這個(gè)功能。

于是定義了一個(gè)字典，鍵就是節(jié)點(diǎn)，值就是節(jié)點(diǎn)在鏈表中的位置。然后便可以知道random指向的節(jié)點(diǎn)在鏈表中的位置了。為了不用每次遍歷鏈表尋找該位置的節(jié)點(diǎn)，我們使用了一個(gè)list存儲(chǔ)所有的節(jié)點(diǎn)，并保持去位置順序不變。這樣就可以根據(jù)位置在常數(shù)級(jí)的時(shí)間內(nèi)找到節(jié)點(diǎn)，然后完成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í)候倒數(shù)第4,5行沒有判斷，也就是沒有倒數(shù)第5行，但是這就會(huì)有一個(gè)問題，因?yàn)殒湵碇械膎ext指針除了尾節(jié)點(diǎn)其余的節(jié)點(diǎn)都是有的，但是random指針每個(gè)節(jié)點(diǎn)都有可能沒有，所以直接使用這個(gè)指針作為鍵去索引對(duì)應(yīng)的值是有問題的。最后通過一個(gè)判斷解決了該問題。

Book中的思路

書中給出了一種思路，可以在不適用輔助空間的基礎(chǔ)上完成該功能。

具體是在進(jìn)行節(jié)點(diǎn)復(fù)制時(shí)將每一個(gè)節(jié)點(diǎn)復(fù)制的節(jié)點(diǎn)放到該節(jié)點(diǎn)的后面，當(dāng)完成一遍節(jié)點(diǎn)復(fù)制之后相當(dāng)于將原來的鏈表變?yōu)樵瓉淼囊槐?，每個(gè)節(jié)點(diǎn)在相鄰的位置重復(fù)出現(xiàn)。這樣在進(jìn)行random指針的復(fù)制時(shí)只需要按照原節(jié)點(diǎn)的random指向，將當(dāng)前節(jié)點(diǎn)的random指向原節(jié)點(diǎn)random指針的下一個(gè)節(jié)點(diǎn)即可。

但是在編程時(shí)還是遇到了問題，下面是錯(cuò)誤的程序。

# -*- 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

錯(cuò)誤描述：空。請(qǐng)檢查一下你的代碼，有沒有循環(huán)輸入處理多個(gè)case。點(diǎn)擊查看如何處理多個(gè)case

目前還目前解決，先放一下，回頭再看看。

作者原創(chuàng)，如需轉(zhuǎn)載及其他問題請(qǐng)郵箱聯(lián)系：lwqiang_chn@163.com。
個(gè)人網(wǎng)站：https://www.myqiang.top。