复杂链表的复制

难度: Medium

请实现 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/

Submission

运行时间: 44 ms

内存: 15.6 MB

"""
# 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

        cur = head 
        while cur:
            copied = Node(cur.val)
            copied.next = cur.next
            cur.next = copied
            cur = cur.next.next
        
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next
        
        cur = head
        copied_cur = head.next
        copied_head = head.next
        while cur:
            cur.next = cur.next.next
            cur = cur.next
            if copied_cur.next:
                copied_cur.next = copied_cur.next.next
                copied_cur = copied_cur.next
        return copied_head

Explain

这个题解采用了三步走的策略： 1. 遍历原始链表，对于每个节点，在其后面创建一个新的节点，其值与原节点相同。 2. 再次遍历链表，这次设置新节点的random指针，使其指向原节点random指针所指向的节点的下一个节点（即复制的节点）。 3. 最后，将链表拆分为原链表和复制的链表，返回复制的链表的头节点。

时间复杂度: O(n)

空间复杂度: O(n)

"""
# 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

        cur = head
        while cur:
            copied = Node(cur.val)
            copied.next = cur.next
            cur.next = copied
            cur = cur.next.next

        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next

        cur = head
        copied_cur = head.next
        copied_head = head.next
        while cur:
            cur.next = cur.next.next
            cur = cur.next
            if copied_cur.next:
                copied_cur.next = copied_cur.next.next
                copied_cur = copied_cur.next
        return copied_head

Explore

在第一步中，我们已经为链表的每个节点创建了一个复制节点，并将其插入到每个原节点和其next节点之间。因此，当我们在第二步中设置复制节点的random指针时，可以确信每个原节点的random指针所指向的节点已经在其后面有一个复制节点。这是因为第一步的操作确保了链表中每个节点后都紧跟着它的复制节点，包括原节点random指针所指向的节点。

在第三步拆分链表的过程中，最后一个节点的处理需要特别注意，以确保不会出现连接错误或丢失节点。对于原链表的最后一个节点，它的next应该指向null，同样，复制链表的最后一个节点也应该指向null。在拆分时，我们遍历链表，将每个原节点的next指向其next的next，即恢复原链表的连接，同时也将每个复制节点的next指向其next的next，以构建完整的复制链表。这确保了两个链表在结尾处正确地结束，没有多余或丢失的连接。

在复制具有循环引用的链表时，算法仍然有效。由于每个节点的复制节点都紧接在原节点后面，即使是原节点的random指针指向自身或形成一个环，复制节点的random指针也会正确指向对应的复制节点，保持循环结构不变。例如，如果一个原节点的random指向自己，那么这个节点的复制节点的random也会指向它自己（即原节点的next）。这种方法自然地保留了原链表中的所有循环引用和复杂结构。

是的，如果输入的原链表为空，即head为None，那么按照题解中的函数实现，返回的确实是None。这是符合预期的，因为没有节点可以复制。验证这一行为的正确性可以通过单元测试，例如传递一个空链表给函数，并检查返回值是否为None。这样可以确认函数在面对空输入时的行为是按预期工作的。