首页 / JAVA / [LeetCode][JavaScript]Copy List with Random Pointer

[LeetCode][JavaScript]Copy List with Random Pointer

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[LeetCode][JavaScript]Copy List with Random Pointer，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2158字，纯文字阅读大概需要4分钟。

内容图文

Copy List with Random Pointer

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.

 
 
 
 
 
 
第一把直接暴力两轮遍历。第一轮遍历copy链表，用hash表记录下各个节点，第二乱遍历去赋值链表里的random对象。
然后稍稍改进了一下，一次遍历里把能的找到的random都赋上，如果还没new出来，记到missed数组中，最后把missed的节点中的random再赋上值。
 
旧版:
                             1
                            var copyRandomList = function(head) {
 2var dict = {};
 3var originNode = head;
 4var newNode = new RandomListNode(0);
 5var originHead = head;
 6var newHead = newNode;
 7while(originNode !== null){
 8var temp = new RandomListNode(originNode.label);
 9            dict[originNode.label] = temp;
10            newNode.next = temp;
1112         newNode = newNode.next;
13         originNode = originNode.next;
14    }
1516     originNode = originHead;
17     newNode = newHead.next;
18while(originNode !== null){
19if(originNode.random !== null){
20             newNode.random = dict[originNode.random.label];
21        }
22         newNode = newNode.next;
23         originNode = originNode.next;
24    }
25return newHead.next;    
26 };

新版:

                             1
                            /*
                            *

                             2
                             * Definition for singly-linked list with a random pointer.

                             3
                             * function RandomListNode(label) {

                             4
                             *     this.label = label;

                             5
                             *     this.next = this.random = null;

                             6
                             * }

                             7
                            */
                             8
                             9
                            /*
                            *

                            10
                             * @param {RandomListNode} head

                            11
                             * @return {RandomListNode}

                            12
                            */
                            13
                            var copyRandomList = function(head) {
14var dict = {};
15var missed = [];
16var originNode = head;
17var newNode = new RandomListNode(0);
18var originHead = head;
19var newHead = newNode;
20while(originNode !== null){
21var temp = new RandomListNode(originNode.label);
22            dict[originNode.label] = temp;
23            newNode.next = temp;
24            newNode = newNode.next;
2526if(originNode.random !== null){
27if(dict[originNode.random.label]){
28                    newNode.random = dict[originNode.random.label];
29                }else{
30                    newNode.random = originNode.random.label;
31                   missed.push(newNode.label);
32               }
33        }
34         originNode = originNode.next;
35    }
36for(var i = 0; i < missed.length; i++){
37var curr = dict[missed[i]];
38         curr.random = dict[curr.random];
39    }
40return newHead.next;    
41 };

 

 
 

原文：http://www.cnblogs.com/Liok3187/p/4590747.html

内容总结

以上是互联网集市为您收集整理的[LeetCode][JavaScript]Copy List with Random Pointer全部内容，希望文章能够帮你解决[LeetCode][JavaScript]Copy List with Random Pointer所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1247872.html

来源：【匿名】