Lintcode105 Copy List with Random Pointer solution 題解

【題目描述】

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

給出一個連結清單，每個節點包含一個額外增加的随機指針可以指向連結清單中的任何節點或空的節點。

var data = {
    val:1,
    next:{
       val:2,
       next:{
          val:3,
          next:{
              val:4,
              next:null
          } 
       }
    }
};

data.rand = data.next.next;
data.next.rand = null;
data.next.next.rand = null;
data.next.next.next.rand = data;

const copyRandomList = function(head){
    if(head === null){
        return null;
    }
    let cur = head;
    let next = null;

    while(cur !== null){
        next = cur.next;
        cur.next = {};
        cur.next.next = next;
        cur = next;
    }

    cur = head;
    let curCopy = null;

    while(cur !== null){
        next = cur.next.next;
        curCopy = cur.next;
        curCopy.val = cur.val;
        curCopy.rand = (function(){
            if(cur.rand !== null){
                // cur.rand是正本，cur.rand.next是副本，是以傳回的是副本指向
                return cur.rand.next;
            }

            return null;
        })();
        cur = next;
    }

    let res = head.next;
    cur = head;

    while(cur !== null){
        next = cur.next.next;
        curCopy = cur.next;
        cur.next = next;
        curCopy.next = (function(){
            if(next !== null){
                return next.next;
            }

            return null;
        })();
        cur =next;
    }

    return res;
};

var result = copyRandomList(data);
console.log(result);
           

合乎自然而生生不息。。。