题目:

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

示例1:

示例2:

示例3:

示例4:

提示：

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

解题思路

复制拼接+拆分链表

考虑构建原节点 1 -> 新节点 1 -> 原节点 2 -> 新节点 2 -> …… 的拼接链表，如此便可在访问原节点的 random 指向节点的同时找到新对应新节点的 random 指向节点。

图例

复制各节点，构建拼接链表:
构建新链表各节点的 random 指向：
拆分原 / 新链表：
返回新链表的头节点 res 即可

题解:

/*
// 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;
        while(cur != null)
        {
            Node next = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = next;
            cur = next;
        }
     
        //复制随机节点
        cur = head;
        while(cur != null)
        {
            Node curNew = cur.next;
            curNew.random = cur.random == null ? null : cur.random.next;
            cur = cur.next.next;
        }
        //拆分链表
        Node headNew = head.next;
        cur = head;
        Node curNew = head.next;
        while(cur != null)
        {
            cur.next = cur.next.next;
            cur = cur.next;
            curNew.next = cur ==null?null:cur.next;
            curNew = curNew.next;
        }
        return headNew;
    }
}