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

 
这个题目有个很巧妙的解法，可以达到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-2-3链表变成1-1-2-2-3-3，每个节点都复制一个其克隆节点。

第二步，将复制的克隆节点的random赋值。

第三步，将链表剥离，恢复原链表，并产生复制链表。
代码
/*
// 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;
        }
        Node cur = head;
        Node pre =new Node(-1);
        //复制节点，1-2-3变为1-1-2-2-3-3
        while(cur != null){
            //深拷贝需要创建新节点
            Node node =new Node(cur.val);
            node.next = cur.next;
            cur.next = node;
            cur = node.next;
        }
        cur = head;
        //处理克隆节点的random
        while(cur!= null){
             if (cur.random != null){
                 cur.next.random = cur.random.next;
             }
            cur = cur.next.next;
        }
        
        
        cur = head.next;
        //保存复制链表的头节点
        Node cloneHead = head.next;
        Node now = head;
        //将链表分离，恢复原始链表，并剥离出新复制链表
        while(cur.next != null){
            now.next = now.next.next;
            cur.next = cur.next.next;
            cur = cur.next;
            now = now.next;
        }
        // 单独处理原链表尾节点
        now.next = null; 
        return cloneHead;
    }
}

import java.util.*;

//复制复制链表
public class P2 {
    public static class Node{
        int val;
        Node next;
        Node random;
    }
    //复制复制链表方法、一
    static Node copy(Node head){
        Node p=head;
        while(p!=null){
            Node q=new Node();
            q.val=p.val;
            q.next=p.next;  // 把q插到p的后边
            p.next=q;
            p=q.next;
        }
        p=head;
        while(p!=null){
            Node q=p.next;
            if(p.random!=null){
                q.random=p.random.next;
            }else{
                q.random=null;
            }
            p=q.next;
        }
        //第三步把两个链表拆开 省略
        return head;
    }
    //复制复制链表方法二
    Node copy2(Node head){
        Node p=head;
        Node result=null;
        Node last=null;
        Map<Node,Node> map=new HashMap<>();
        while(p!=null){
            Node q=new Node();
            q.val=p.val;
            if(result==null){
                result=q;
            }else{
                last.next=q;
            }
            last=q;
            map.put(p,q);
            p=q.next;
        }
        p=head;
        Node q=result;
        while(p!=null){
            q.random=map.get(p.random);
            p=p.next;
        }
        return result;
    }
}


 

题目描述
请实现 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)