劍指offer：復雜鏈表的復制

題目描述
輸入一個復雜鏈表（每個節點中有節點值，以及兩個指針，一個指向下一個節點，另一個特殊指針指向任意一個節點），返回結果為復制后復雜鏈表的head。（注意，輸出結果中請不要返回參數中的節點引用，否則判題程序會直接返回空）

# -*- 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：
    直接復制鏈表的話，由于每個節點有一個隨機指針指向任意的位置(包括空指針)，因此如果用最樸素的方法
    來解決，需要在將所有節點復制完之后，對每個節點的random屬性遍歷一次整個鏈表，因此假設共有n個
    節點，那么這種最樸素的解法的時間復雜度為O(n^2)

    解法2：
    解法1之所以效率低是因為每個節點的random指針的指向需要遍歷整個鏈表才能找到，如果我們犧牲空間來
    換時間的話，那么就可以做到時間復雜度為O(n), 額外使用空間O(n)。
    具體做法可以是用一個字典來保存每個節點及其對應的克隆節點的地址，這樣就可以通過查詢這個哈希表在
    O(1)的時間內找到random指針所指向的節點

    解法3：
    解法2之所以能把時間復雜度降下來，是因為保存了原始節點和對應克隆節點的位置關系，因此可以很快找到
    原始節點對應的克隆節點在哪。如果我們在復制鏈表的時候就讓克隆節點跟在原始節點后面，那么就可以在
    不額外使用哈希表的情況下做到時間復雜度為O(n)了
"""

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

        pNode = pHead
        pNode = pNode.next
        cloneNode = pClone
        # 這個循環用于將原始鏈表復制出來，但是先忽略random指針，關鍵在于要用這個字典保存
        # 原始節點和對應克隆節點的地址
        while pNode:
            cloneNode.next = RandomListNode(pNode.label)
            nodeTable[id(pNode)] = cloneNode.next
            cloneNode = cloneNode.next
            pNode = pNode.next

        # 根據字典保存的信息設置克隆鏈表的random指針
        cloneNode = pClone
        while pHead:
            # 需要注意的是random指針可能是指向None，而我們在字典中并沒有保存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. 復制整個鏈表，這里先忽略random指針的指向，得到形如A->A'->B->B'->C->C'的復制結果
        # 2. 設置克隆節點的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'）
        然后進入循環就不能通過牛客的OJ，

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

        這兩種方法在本地調試的時候都是沒問題的。
        """
        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()