题目描述

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

解题思路

剑指书上的方法

1.方法一

• 第一步：复制原始链表上的每个节点N、创造N’ ; 把创造出来的节点用 m_pnext链接起来; 把<N,N’>放进哈希表。
• 第二步：设置复制链表上的 m_psibling 。如果原始链表节点N的 m_psibling 指向节点S; 复制链表当中的 N’ 指向 S’ 。

2.方法二

• 第一步：复制链表的节点，将复制的节点接到原始节点的后面
  e.g. 1 -> 1’ -> 2 -> 2’ -> 3 -> 3’
• 第二步：将链表复制节点的 random 指向的指针 (n.next.random)，指向原始节点的后面 (n.random.next)

Leetcode上的方法

• 题意的复制是指『深拷贝』（Deep Copy）<=> 浅拷贝（Shallow Copy）
  • 浅拷贝只复制了某个对象的指针，而不复制对象本身，共享同一块内存。 => newhead = head （这只是将指针指到了 head）
  • 深拷贝要创造一个一模一样的对象，新对象跟旧对象不共享内存，修改新对象不会改到原对象。

• 用 DFS（Depth-First Search）的递归解法
  • 将已经存在的节点存入 Hash Table。
  • 从最深的一个节点开始复制。
  • 在写逻辑的时候，思考最后一步的要件（判断逻辑 & 返回），递归解法都是如此操作。

Python代码

"""
# 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 not head:
            return None
        n = head
        # next指针：1->1'->2->2'->3->3'
        while n:
            node = Node(n.val)
            node.next = n.next
            n.next = node
            n = node.next
       
        # random指针
        n = head
        while n:
            if not n.random:
                n.next.random = None
            else:
                n.next.random = n.random.next # 这边是回到原始n链表的随机的下一个复制的点
            n = n.next.next

        # 跨号返回
        n = head.next
        while n.next:
            n.next = n.next.next
            n = n.next
        return head.next
		
		
		"""
		Leetcode方法：用DFS解
		"""
        def dfs(head):
            if not head:
                return None
            if head in visited:
                return visited[head] 
            
            # Deep Copy：创建复制的新节点
            copy = Node(head.val)
            visited[head] = copy
            copy.next = dfs(head.next)
            copy.random = dfs(head.random)
            return copy
        visited = {}
        return dfs(head)

题目：已知一链表，每个节点除了有一个指向下一节点的指针外，还有一随机指针指向链表中的任意节点（可能为空，也有可能为自身），请复制一个链表，要求节点的顺序以及节点上的随机指针指向的节点位置和原链表一致。

这个题目有个很巧妙的解法，可以达到O(n)的效率，其中心思想是把原始链表和复制链表先合并为一个有固定顺序的链表，然后给复制链表中每个节点的随机指针复制，最后再打断链表恢复原样。

typedef struct Node {
    int nData;
    Node* pNext;
    Node* pRandom;
} Node;

Node* DuplicateList(Node* pSrcListHead)
{
    if (pSrcListHead == NULL)
        return NULL;
 
    Node* pNode = pSrcListHead;
    while (pNode != NULL)
    {
        Node* pNewNode = new Node;
        pNewNode->nData = pNode->nData;
        pNewNode->pNext = pNode->pNext;
        pNewNode->pRandom = pNode->pRandom;

        pNode->pNext = pNewNode;
        pNode = pNewNode->pNext;
    }
 
    Node* pDestListHead = pSrcListHead->pNext;

    pNode = pSrcListHead;
    while (pNode != NULL)
    {
        pNode->pNext->pRandom = pNode->pRandom->pNext;
        pNode = pNode->pNext->pNext;
    }

    pNode = pSrcListHead;
    Node* pNode2 = pNode->pNext;
    while (pNode != NULL)
    {
        pNode->pNext = pNode2->pNext;
        pNode = pNode->pNext;

        if (pNode)
            pNode2->pNext = pNode->pNext;
        else
            pNode2->pNext = NULL;

        pNode2 = pNode2->pNext;
    }

    return pDestListHead;
}

    不过目前还未考虑到原始链表有环的情况，如果原始链表有环，则应该先求出环的入口点，然后利用上面的方法进行链表复制。

原文地址：http://hi.baidu.com/%B3%A3%D1%C5%C3%F4/blog/item/173d50ae523a0ede7dd92a63.html

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

分析：

方法1：哈希表

该题的难点在于 random 指针的复制，因为 random 指针可能会指向前面的节点，因此我们可以定义一个哈希表来存储复制的节点，键为旧节点，值为新节点，第一次遍历先复制链表的节点，第二次遍历复制链表的指针。

时间复杂度：O(n)
空间复杂度：O(n)

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        //创建哈希表
        HashMap<Node, Node> map = new HashMap<>();
        //遍历链表，复制节点，旧节点作为键，新节点作为值
        Node cur = head;
        while(cur != null){
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        //再次遍历链表，复制指针
        cur = head;
        while(cur != null){
            //获取对应复制的节点
            Node node = map.get(cur);
            //复制 next 和 random 指针
            node.next = map.getOrDefault(cur.next, null);
            node.random = map.getOrDefault(cur.random, null);
            //继续遍历下一个节点
            cur = cur.next;
        }
        //返回对应复制的节点，头节点为空时返回空
        return map.getOrDefault(head, null);
    }
}

方法2：拼装+拆分

方法1 虽然实现起来较为简单，但面试的时候还是喜欢考验在原链表上进行操作，且空间复杂度较小，因此我们可以用到拼装的方法，在每个节点之间复制一个新的节点，拿 head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 举例：

• 旧链表：    7 → 13 → 11 → 10 → 1
• 拼装链表：7 → 7* → 13 → 13* → 11 → 11* → 10 → 10* → 1 → 1*

这样就得一个拼装的链表，这样的链表满足一个特性，原链表节点（node）的 next 是指向新复制的一个节点的，因此新节点的 random 指针可以指向旧节点  random 指针的 next，即：node.next.random = node.random.next，这样就可以实现 random 的复制操作。

最后，我们再将拼装链表拆分回旧链表和新复制的链表即可，拆分可以用 node.next = node.next.next，但是注意旧链表的操作一定要在新链表之前，并且要把最后一个节点的指针指向空，因为本来指的新节点。

时间复杂度：O(n)
空间复杂度：O(1)

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        //空节点直接返回空
        if(head == null){
            return null;
        }
        //第一次遍历，复制并拼接新节点
        for(Node node = head; node != null; node = node.next.next){
            //复制节点
            Node next = new Node(node.val);
            //拼接
            next.next = node.next;
            node.next = next;
        }
        //第二次遍历，复制 random
        for(Node node = head; node != null; node = node.next.next){
            if(node.random != null){
                node.next.random = node.random.next;
            }
        }
        //定义新旧节点
        Node cur = head.next, pre = head, ans = cur;
        //第三次遍历，将缝合链表拆分成旧链表和新链表
        while(cur.next != null){
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre = pre.next;
            cur = cur.next;
        }
        //令旧节点最后一个节点指向空
        pre.next = null;
        return ans;
    }
}

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof