首页 > 代码库 > 138. Copy List with Random Pointer
138. 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.
常规解法：
必须先遍历一遍复制single linked list。遍历过程中建立一个1对1的map，copy的每个node都是以之前node为key的pair的value。这样在第二次遍历的时候，只需要将random赋值就好。
public RandomListNode CopyRandomList(RandomListNode head) { if(head == null) return null; RandomListNode nextNode = null; var sentinel = new RandomListNode(-1); sentinel.next = head; var sentinel2 = new RandomListNode(-1); var dummy = sentinel2; var hashtable = new Dictionary<RandomListNode,RandomListNode>(); //copy; while(head != null) { var newCopy = new RandomListNode(head.label); hashtable.Add(head,newCopy); sentinel2.next = newCopy; head = head.next; sentinel2 = sentinel2.next; } //copy random var newHead = sentinel.next; var newListHead = dummy.next; while(newHead != null) { var random = newHead.random; newListHead.random =(random==null)?null: hashtable[random]; newHead = newHead.next; newListHead = newListHead.next; } return dummy.next; }
网上有大神http://fisherlei.blogspot.com/2013/11/leetcode-copy-list-with-random-pointer.html 给出了很巧妙的方法。
public RandomListNode CopyRandomList(RandomListNode head) { if(head == null) return null; RandomListNode nextNode = null; var sentinel = new RandomListNode(-1); sentinel.next = head; //copy; while(head != null) { var newCopy = new RandomListNode(head.label); nextNode = head.next; head.next = newCopy; newCopy.next = nextNode; head = nextNode; } //copy random var newHead = sentinel.next; while(newHead != null) { var random = newHead.random; var follow = newHead.next; follow.random =(random==null)? null:random.next; newHead = follow.next; } //split into 2 lists var legacy = sentinel.next; var pilot = new RandomListNode(-1); var dummy = pilot; while(legacy != null) { pilot.next = legacy.next; pilot = pilot.next; legacy.next = legacy.next.next ; legacy = legacy.next; } return dummy.next; }
138. Copy List with Random Pointer
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。