剑指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()