剑指 Offer 35. 复杂链表的复制

剑指 Offer 35. 复杂链表的复制

题目描述：

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

示例：

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

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

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

思路：

参考链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/solution/jian-zhi-offer35fu-za-lian-biao-de-fu-zhi-by-lisa-/

代码：

var copyRandomList = function(head) {
    if(!head) return head;
    //第一步，复制链表节点 1->2->3  变成 1->1->2->2->3->3
    for(let p=head,copy=null;p!=null;p=p.next.next){
        copy=new Node(p.val);
        copy.next=p.next;
        p.next=copy;
    }
    //random指针的复制
    for(let p=head;p!==null;p=p.next.next){
        if(p.random!==null){
            p.next.random=p.random.next;
        }
    }
   //分离出链表
   let newHead=head.next;
   for(let p=head;p&&p.next;){
       let cur=p.next;
       p.next=cur.next;
       p=cur;
   }
   return newHead;
};