本文共 1871 字，大约阅读时间需要 6 分钟。

题目描述

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

java

大问题拆成三个小问题逐个击破

/*// 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) {
           copyNodes(head);        copyRandomNodes(head);        return reconnectNodes(head);    }    //第1步:复制所有基础节点，每个节点复制在原节点的后边    public void copyNodes(Node head){
           Node cur=head;        //创建新节点        while(cur!=null){
               Node copy=new Node(cur.val);            copy.next=cur.next;            cur.next=copy;            cur=copy.next;        }    }    //第2步： 将每个节点的随机指针也复制，
   
    ,则
    
         public void copyRandomNodes(Node head){
               Node cur=head;            while(cur!=null){
                   Node copy_node=cur.next;  //复制的节点                if(cur.random!=null){
      //这个if语句要注意                    copy_node.random=cur.random.next;  //复制节点的random节点是原节点的random节点的netx节点                }                cur=copy_node.next;            }    }    //第3步，拆成两个链表。 奇数节点属于原始链表；偶数节点属于复制链表    public Node reconnectNodes(Node head){
               Node cur=head;            Node copy_head=null;            Node copy_node=null;            if(cur!=null){
                   copy_head=cur.next;                copy_node=cur.next;                cur.next=copy_head.next;                cur=cur.next;            }            while(cur!=null){
                   copy_node.next=cur.next;                copy_node=copy_node.next;                cur.next=copy_node.next;                cur=cur.next;            }            return  copy_head;    }}