12 - Hard - 复制带随机指针的链表

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深度拷贝。

Solution 1

构建一个dict，存储{label：[node,...]}，作为random的检索基础
然后构建一个list，顺序存储所有random指向的节点在dict中位置，[(label, pos), None, ...]，然后建立新链表，random不赋值
然后再新链表上再次构建dict同上，最后顺序遍历list，取出相关位置，并让random指向对应的新节点

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        node_dict = {}
        p = head
        random_list = []
        dummy = RandomListNode(0)
        pp = dummy
        while p:
            if p.label not in node_dict:
                node_dict[p.label] = []
            node_dict[p.label].append(p)
            pp.next = RandomListNode(p.label)
            pp = pp.next
            p = p.next
            
        p = head
        while p:
            temp = None
            if p.random:
                for i, _node in enumerate(node_dict[p.random.label]):
                    if p.random is _node:
                        temp = (p.random.label, i)
            random_list.append(temp)
            p = p.next
            
        pp = dummy.next
        node_dict = {}
        while pp:
            if pp.label not in node_dict:
                node_dict[pp.label] = []
            node_dict[pp.label].append(pp)
            pp = pp.next
            
        pp = dummy.next
        i = 0
        while pp:
            temp = random_list[i]
            if temp:
                pp.random = node_dict[temp[0]][temp[1]]
            else:
                pp.random = None
            pp = pp.next
            i += 1
        return dummy.next

Solution 2
1）建立新节点，每个新节点插在旧节点的后面
2）遍历完整链表，后一个节点的random赋值为前一个节点的random.next
3）遍历链表，拆分

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if not head:
            return head
        self.copyNodes(head)
        self.connectRandomNodes(head)
        return self.reconnectRandomNodes(head)

    def copyNodes(self, head):
        node = head
        while node:
            cloned = RandomListNode(0)
            cloned.label = node.label
            cloned.next = node.next
            node.next = cloned
            node = cloned.next

    def connectRandomNodes(self, head):
        node = head
        while node:
            cloned = node.next
            if node.random:
                cloned.random = node.random.next
            node = cloned.next

    def reconnectRandomNodes(self, head):
        node = head
        clonedHead = clonedNode = node.next
        node.next = clonedHead.next
        node = node.next

        while node:
            clonedNode.next = node.next
            clonedNode = clonedNode.next
            node.next = clonedNode.next
            node = node.next

        return clonedHead