138. 复制带随机指针的链表

题目描述

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

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

我的解法（AC）

# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if(not head):
            return None
        if(not head.next):
            temp = RandomListNode(head.label)
            if(head.random):
                temp.random = temp
            return temp
        
        now = head
        while(now):
            temp = RandomListNode(now.label)
            temp.next = now.next
            now.next = temp
            now = temp.next
        

        now = head
        while(now):
            next = now.next
            if(not now.random):
                next.random = None
            else:
                next.random = now.random.next
            now = now.next.next
            
        res_head = head.next
        res_tail = head.next
        now = head.next.next
        head.next = now
        
        while(now):
            temp = now
            now = now.next
            res_tail.next = now
            now = now.next
            temp.next = now
            res_tail = res_tail.next
        res_tail.next = None
        
        return res_head