Jianbo Dai's

jz035.复杂链表的复制

 
  • Jun 21, 2020

题目链接

这个题，有一种思路是将此复杂链表看成一个图，图的基本单位是顶点，顶点之间的关联关系为边。由于图的遍历方式有深度优先搜索和广度优先搜索，同样地，对于此链表也可以使用深度优先搜索与广度优先搜索两种方式进行遍历。算法1中展示的就是用dfs解答。首先从头节点开始拷贝，使用递归拷贝所有的next节点，再递归拷贝所有的random节点。在拷贝每个节点的时候，有两种情况，一是如果某个节点没有被拷贝，则创建一个新的节点进行拷贝，并将拷贝过的节点保存在哈希表中；另一种情况是，如果某个节点已经被拷贝过了，则不需要被重复拷贝。这个算法的时间复杂度是O（N），空间复杂度是O（N）。至于用bfs遍历图的算法我就没有记录，主要是因为懒。

还有一种更加优化的算法如2，在不用辅助空间的情况下实现O（N）的时间效率。该方法的第一步是根据原始链表的每个节点N创建对应的节点N‘，但是特殊之处在于将N’链接在N后面。第二步复制random节点。第三步是，将建立好的长链表拆分称两个链表，把奇数位置的节点相连接起来就是原始链表，把偶数位置的节点想链接起来就是复制出来的链表。这个算法的时间复杂度是O（N），空间复杂度是O（1）。

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""
class Solution:

    def copyRandomList1(self, head: 'Node') -> 'Node':
        self.visited = {}
        return self.dfs(head)

    def dfs(self, node):
        if not node:
            return None
        if node in self.visited:
            return self.visited[node]
        copy = Node(node.val, None, None)
        self.visited[node] = copy
        copy.next = self.dfs(node.next)
        copy.random = self.dfs(node.random)
        return copy

    def copyRandomList2(self, head: 'Node') -> 'Node':
        if not head:
            return None

        cur = head
        while cur:
            new_node = Node(cur.val, None, None)
            new_node.next = cur.next
            cur.next = new_node
            cur = new_node.next
        
        cur = head
        while cur:
            cur.next.random = cur.random.next if cur.random else None
            cur = cur.next.next
        
        cur_old = head
        cur_new = new_head = head.next
        while cur_old:
            cur_old.next = cur_old.next.next
            cur_new.next = cur_new.next.next if cur_new.next else None
            cur_old = cur_old.next
            cur_new = cur_new.next
        return new_head
Search