題目描述
輸入一個(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ì)直接返回空）

靈寶網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)建站！從網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、響應(yīng)式網(wǎng)站開發(fā)等網(wǎng)站項(xiàng)目制作，到程序開發(fā)，運(yùn)營維護(hù)。創(chuàng)新互聯(lián)建站自2013年起到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)建站。

# -*- coding: utf-8 -*-
# @Time         : 2019-07-05 15:52
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : complexListNodeClone.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

class RandomListNode:
    def __init__(self, x):
        self.label = x
        self.next = None
        self.random = None

"""
    解法1：
    直接復(fù)制鏈表的話，由于每個(gè)節(jié)點(diǎn)有一個(gè)隨機(jī)指針指向任意的位置(包括空指針)，因此如果用最樸素的方法
    來解決，需要在將所有節(jié)點(diǎn)復(fù)制完之后，對(duì)每個(gè)節(jié)點(diǎn)的random屬性遍歷一次整個(gè)鏈表，因此假設(shè)共有n個(gè)
    節(jié)點(diǎn)，那么這種最樸素的解法的時(shí)間復(fù)雜度為O(n^2)

    解法2：
    解法1之所以效率低是因?yàn)槊總€(gè)節(jié)點(diǎn)的random指針的指向需要遍歷整個(gè)鏈表才能找到，如果我們犧牲空間來
    換時(shí)間的話，那么就可以做到時(shí)間復(fù)雜度為O(n), 額外使用空間O(n)。
    具體做法可以是用一個(gè)字典來保存每個(gè)節(jié)點(diǎn)及其對(duì)應(yīng)的克隆節(jié)點(diǎn)的地址，這樣就可以通過查詢這個(gè)哈希表在
    O(1)的時(shí)間內(nèi)找到random指針?biāo)赶虻墓?jié)點(diǎn)

    解法3：
    解法2之所以能把時(shí)間復(fù)雜度降下來，是因?yàn)楸４媪嗽脊?jié)點(diǎn)和對(duì)應(yīng)克隆節(jié)點(diǎn)的位置關(guān)系，因此可以很快找到
    原始節(jié)點(diǎn)對(duì)應(yīng)的克隆節(jié)點(diǎn)在哪。如果我們?cè)趶?fù)制鏈表的時(shí)候就讓克隆節(jié)點(diǎn)跟在原始節(jié)點(diǎn)后面，那么就可以在
    不額外使用哈希表的情況下做到時(shí)間復(fù)雜度為O(n)了
"""

class Solution2:
    def Clone(self, pHead):
        if not pHead:
            return None
        nodeTable = dict()  # 用于保存原始節(jié)點(diǎn)對(duì)應(yīng)的克隆節(jié)點(diǎn)的地址
        pClone = RandomListNode(pHead.label)
        # 由于節(jié)點(diǎn)類型無法哈希，因此用地址作為key
        nodeTable[id(pHead)] = pClone

        pNode = pHead
        pNode = pNode.next
        cloneNode = pClone
        # 這個(gè)循環(huán)用于將原始鏈表復(fù)制出來，但是先忽略random指針，關(guān)鍵在于要用這個(gè)字典保存
        # 原始節(jié)點(diǎn)和對(duì)應(yīng)克隆節(jié)點(diǎn)的地址
        while pNode:
            cloneNode.next = RandomListNode(pNode.label)
            nodeTable[id(pNode)] = cloneNode.next
            cloneNode = cloneNode.next
            pNode = pNode.next

        # 根據(jù)字典保存的信息設(shè)置克隆鏈表的random指針
        cloneNode = pClone
        while pHead:
            # 需要注意的是random指針可能是指向None，而我們?cè)谧值渲胁]有保存None的key
            if pHead.random:
                cloneNode.random = nodeTable[id(pHead.random)]
            pHead = pHead.next
            cloneNode = cloneNode.next

        return pClone

class Solution3:
    def Clone(self, pHead):
        # 解法3的思路可以分為三步：
        # 1. 復(fù)制整個(gè)鏈表，這里先忽略random指針的指向，得到形如A->A'->B->B'->C->C'的復(fù)制結(jié)果
        # 2. 設(shè)置克隆節(jié)點(diǎn)的random指針
        # 3. 將鏈表拆分成原始鏈表和克隆鏈表
        self.cloneNode(pHead)
        self.connectSiblingNode(pHead)
        return self.reconnectNode(pHead)

    def cloneNode(self, pHead):
        pNode = pHead
        while pNode:
            pClone = RandomListNode(pNode.label)
            pClone.next = pNode.next
            pNode.next = pClone
            pNode = pClone.next

    def connectSiblingNode(self, pHead):
        pNode = pHead
        while pNode:
            clone_head = pNode.next
            if pNode.random:
                clone_head.random = pNode.random.next
            pNode = clone_head.next

    def reconnectNode(self, pHead):
        if not pHead:
            return None
        new_head = pHead.next
        pNode = new_head
        """
        這里不知為什么，如果把pHead指向new_head的左邊（即pHead和new_head分別指向A和A'）
        然后進(jìn)入循環(huán)就不能通過牛客的OJ，

        但是將pHead指向new_head的右邊（即pHead和new_head分別指向B和A'）
        然后進(jìn)入循環(huán)就可以通過。

        這兩種方法在本地調(diào)試的時(shí)候都是沒問題的。
        """
        pHead.next = pNode.next
        pHead = pHead.next
        while pHead:
            pNode.next = pHead.next
            pNode = pNode.next
            pHead.next = pNode.next
            pHead = pHead.next

        return new_head

def main():
    # 1->3
    # 2->1
    # 3->2
    # node = RandomListNode(1)
    # node.next = RandomListNode(2)
    # node.next.next = RandomListNode(3)
    # node.random = node.next.next
    # node.next.random = node
    # node.next.next.random = node.next

    node1 = RandomListNode(1)
    node2 = RandomListNode(2)
    node3 = RandomListNode(3)
    node4 = RandomListNode(4)
    node5 = RandomListNode(5)
    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5
    node1.random = node3
    node2.random = node5
    node4.random = node2

    solution = Solution2()
    head = solution.Clone(node1)
    while head:
        if head.random:
            print(head.label, head.random.label)
        else:
            print(head.label, 'None')
        head = head.next

if __name__ == '__main__':
    main()

文章標(biāo)題：劍指offer：復(fù)雜鏈表的復(fù)制
本文路徑：http://www.kartarina.com/article4/jecpoe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供手機(jī)網(wǎng)站建設(shè)、網(wǎng)站內(nèi)鏈、ChatGPT、Google、云服務(wù)器、移動(dòng)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)