很多读者可能都知道“各个击破”的军事思想，这种思想的精髓是当敌我实力悬殊时，我们可以把强大的敌人分割开来，然后集中优势兵力打败被分割开来的小部分敌人。要一下子战胜总体很强大的敌人很困难，但战胜小股敌人就容易多了。同样，在面试中，当我们遇到复杂的大问题的时候，如果能够先把大问题分解成若干个简单的小问题，然后再逐个解决这些小问题，则可能也会容易很多。

Question

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

示例 1：

1 2	`输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]`

示例 2：

1 2	`输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]`

示例 3：

1 2	`输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]`

示例 4：

1
2
3

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：-10000 <= Node.val <= 10000；Node.random 为空（null）或指向链表中的节点；节点数不超过1000 。

Intuition

初步思想

把复制过程分成两步：第一步是复制原始链表上的每个节点，并用next指针链接起来；第二步是设置每个节点的random指针。假设原始链表中的某个节点N的 random 指针指向节点S，由于S在链表中可能在N的前面也可能在N的后面，所以要定位S的位置需要从原始链表的头节点开始找。对于一个含有n个节点的链表，由于定位每个节点的random指针都需要从链表头节点开始经过 \(O(n)\)步才能找到，因此这种方法总的时间复杂度是 \(O(n^2)\)。

进阶思想

由于上述方法的时间主要花费在定位节点的random指针上面，我们试着在这方面去进行优化。我们还是分为两步：第一步仍然是复制原始链表上的每个节点N创建N'，然后把这些创建出来的节点用next指针链接起来。同时我们把<N, N>的配对信息放到一个哈希表中；第二步还是设置复制链表上每个节点的random指针。如果在原始链表中节点N的random指针指向节点S，那么在复制链表中，对应的N'应该指向S'。由于有了哈希表，我们可以用 \(O(1)\) 的时间根据S找到S'。第二种方法相当于用空间换时间。对于有n个节点的链表，我们需要一个大小为 \(O(n)\) 的哈希表，也就是说我们以\(O(n)\) 的空间消耗把时间复杂度由 \(O(n^2)\) 降低到 \(O(n)\)。

剑指offer终极思想

第三种方法的第一步仍然是根据原始链表的每个节点N创建对应的N'。这一次，我们把N'链接在N的后面。如图所示：

第二步设置复制出节点的random指针。假设原始链表上的N的random指针指向节点S(N.random = S)，那么其对应复制出来的N'是N的next指针指向的节点(N.next = N')，同样S'也是S(S.next = S')的next指针指向的节点。用一行代码就能实现 N.random 到S'的连接， N'.random = N.random.next。（此处是关键！）如图所示：

第三步把这个长链表拆分成两个链表：把奇数位置的节点用next指针链接起来就是原始链表，把偶数位置的节点用next指针链接起来就是复制出来的链表。如图所示：

测试用例

功能测试（节点中的random指针指向节点自身；两个节点的random指针形成环状结构；链表中只有一个节点）。特殊输入测试（指向链表头节点的指针为 nullptr 指针）。

本题考点

考查应聘者对复杂问题的思维能力。本题中的复杂链表是一种不太常见的数据结构，而且复制这种链表的过程也较为复杂。我们把复杂链表的复制过程分解成3个步骤，同时把每个步骤都用图形化的方式表示出来，这样能帮助我们厘清思路。在写代码的时候，我们为每个步骤定义一个子函数，最后在复制函数中先后调用这3个函数。有了这些清晰的思路之后再写代码，就容易多了。 考查应聘者分析时间效率和空间效率的能力。当应聘者提出第一种和第二种思路的时候，面试官会提示此时在效率上还不是最优解。这时候应聘者要能自己分析出这两种算法的时间复杂度和空间复杂度各是多少。

Code

"""
# 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 cloneNode(self, head):
        p = head
        while p:
            tmp = Node(p.val)
            tmp.next = p.next
            p.next = tmp
            p = tmp.next

    def connectRandom(self, head):
        p = head
        while p:  
            p_cloned = p.next
            # p.random可能会指向None 所以这里这么写 if p.random else None
            p_cloned.random = p.random.next if p.random else None
            p = p.next.next
    
    def splitLinkedList(self, head):
        dummy = Node(0)
        cloned_p = head.next
        dummy.next = head.next

        while cloned_p.next:
            tmp = cloned_p.next.next
            cloned_p.next = tmp
            cloned_p = tmp

        return dummy.next

    def copyRandomList(self, head: 'Node') -> 'Node':
        if head == None:  return None
        
        # 复制节点
        self.cloneNode(head)
        
        # 复制出节点的random指针
        self.connectRandom(head)

        # 拆分链表
        return self.splitLinkedList(head)

LeetCode 剑指offer

链表

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LeetCode 236. 二叉树的最近公共祖先（中）& 剑指offer 面试题68 - II. 二叉树的最近公共祖先（易）上一篇

剑指offer 面试题34. 二叉树中和为某一值的路径（中）& LeetCode 113. 路径总和 II（中）下一篇

剑指offer 面试题35. 复杂链表的复制（中）& LeetCode 138. 复制带随机指针的链表（中）

Question

Intuition

Code