138.md

138. Copy List with Random Pointer

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/copy-list-with-random-pointer/

内容描述

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

解题方案

思路 1 - 时间复杂度: O(N) - 空间复杂度: O(N)

用一个字典将原node和copy的node记录下来，格式为{node: copy_node}

beats 98.04%

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if not head:
            return head
        
        dummy, lookup = head, {}
        while dummy:
            lookup[dummy] = RandomListNode(dummy.label)
            dummy = dummy.next
            
        dummy = head
        while dummy:
            if dummy.random:
                lookup[dummy].random = lookup[dummy.random]  # 类比 dummy.random = dummy.random
            if dummy.next:
                lookup[dummy].next = lookup[dummy.next]  # 类比 dummy.next = dummy.next
            dummy = dummy.next
            
        return lookup[head]

思路 2 - 时间复杂度: O(N) - 空间复杂度: O(1)

我们可以做到O(1)，用一个技巧：

• 第一步就是我们将原来的 LinkedList 变成 node1 -> copy_node1 -> node2 -> copy_node2 的形式
• 第二步我们对新的 twisted LinkedList 做一次循环，然后将所有的 random 赋值好
• 第三步恢复原来的 LinkedList 并且返回我们的 deep copy LinkedList 的 head

参考caikehe

beats 21.51%

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if not head:
            return head
        # copy nodes
        cur = head
        while cur:
            nxt = cur.next
            cur.next = RandomListNode(cur.label)
            cur.next.next = nxt
            cur = nxt
        # copy random pointers
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next
        # separate two parts, note we have to recover the original linkedList
        dummy = cur = head.next
        while cur.next:
            head.next = cur.next
            head = head.next
            cur.next = head.next
            cur = cur.next
        head.next = None
        return dummy