剑指 Offer 35. 复杂链表的复制 #

问题描述#

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 4：
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
提示：

-10000 <= Node.val <= 10000

Node.random 为空（null）或指向链表中的节点。

节点数目不超过 1000 。

注意：本题与主站 138 题相同：https://leetcode-cn.com/problems/copy-list-with-random-pointer/

解题思路#

显然问题的关键是确定 random 指针指向的结点。

可以记录整个链表的长度 num_nodes，然后计算 random 结点到链表尾结点的长度 to_tail，将 num_nodes 减去 to_tail 得到的长度就是 random 结点到链表头结点的距离。

# 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 copyRandomList(self, head: 'Node') -> 'Node':
        if head is None:
            return None

        new_head = Node(head.val)
        new_p = new_head
        p = head.next

        num_nodes = 1
        while p:
            num_nodes += 1
            new_p.next = Node(p.val)
            new_p = new_p.next
            p = p.next

        new_p = new_head
        p = head
        while p:
            if p.random is None:
                new_p.random = None
            else:
                to_tail = 0
                r = p.random
                while r:
                    to_tail += 1
                    r = r.next

                from_head = num_nodes - to_tail + 1

                r = new_head
                while from_head - 1:
                    r = r.next
                    from_head -= 1

                new_p.random = r

            p = p.next
            new_p = new_p.next

        return new_head

时间复杂度为 \(\mathcal{O}(n^2)\)。

对于结点 p 和复制的结点 new_p，关键在于建立 p.random 结点和 new_p.random 结点之间的关系，这样获取 p.random 结点的同时也能获取 new_p.random 结点。

上面的方法利用了每个结点在链表中的绝对位置。

也可以使用字典来保存 p.random 到 new_p.random 直接的对应关系。

# 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 copyRandomList(self, head: "Node") -> "Node":
        if head is None:
            return None

        node_map = {}
        p = head
        while p:
            node_map[p] = Node(p.val)
            p = p.next

        p = head
        while p:
            if p.next:
                node_map[p].next = node_map[p.next]
            if p.random:
                node_map[p].random = node_map[p.random]
            p = p.next

        return node_map[head]

random 结点还能直接获取的就是它的 next 结点，所以可以在原链表的每个结点后重复该结点，链表由 A->B->C 变为了 A->A'->B->B'->C->C'，则 new_p.random=p.random.next。

# 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 copyRandomList(self, head: "Node") -> "Node":
        if head is None:
            return None

        # 重复结点
        p = head
        while p:
            new_p = Node(p.val)
            new_p.next = p.next
            p.next = new_p
            p = new_p.next

        # 建立新结点的 random 指针
        p = head
        while p:
            if p.random:
                p.next.random = p.random.next
            p = p.next.next
        p = head.next

        # 删除原结点
        while p and p.next:
            p.next = p.next.next
            p = p.next

        return head.next

剑指 Offer 35. 复杂链表的复制#

问题描述#

解题思路#

剑指 Offer 35. 复杂链表的复制 #