https://leetcode.com/problems/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.

解題思路：

啥叫deep copy，啥叫shallow copy？Java里shallow copy的意思是，B拷貝于A，但B和A指向同一個(gè)對(duì)象。deep copy的意思是，B和A指向不同的對(duì)象，但這兩個(gè)對(duì)象完全一樣。

具體可以參考?http://stackoverflow.com/questions/869033/how-do-i-copy-an-object-in-java

那么這道題目的難度就在于多了一個(gè)random指針。當(dāng)前節(jié)點(diǎn)和next很容易復(fù)制，遍歷一遍，不斷根據(jù)原來鏈表的值去new新節(jié)點(diǎn)，并將next指向下一節(jié)點(diǎn)即可。問題是，第二遍的時(shí)候，如何找到當(dāng)前節(jié)點(diǎn)的random節(jié)點(diǎn)？

這里借用的是HashMap這個(gè)數(shù)據(jù)結(jié)構(gòu)，第一遍遍歷的時(shí)候，建立一個(gè)map，key是原鏈表的節(jié)點(diǎn)，value是當(dāng)前鏈表的節(jié)點(diǎn)。我們知道，實(shí)際上map里存的是相應(yīng)的地址。這樣，第二遍尋找新鏈表當(dāng)前節(jié)點(diǎn)node的random時(shí)，只要在map里找原鏈表對(duì)應(yīng)節(jié)點(diǎn)的value就可以了。

代碼如下：

/*** Definition for singly-linked list with a random pointer.* class RandomListNode {* int label;* RandomListNode next, random;* RandomListNode(int x) { this.label = x; }* };*/ public class Solution {public RandomListNode copyRandomList(RandomListNode head) {if (head == null) {return head;}Map<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();RandomListNode copyHead = new RandomListNode(head.label);RandomListNode head1 = head;RandomListNode returnHead = copyHead;map.put(head1, copyHead);while(head1.next != null) {copyHead.next = new RandomListNode(head1.next.label);map.put(head1.next, copyHead.next);copyHead = copyHead.next;head1 = head1.next;}copyHead = returnHead;head1 = head;while(copyHead != null) {copyHead.random = map.get(head1.random);copyHead = copyHead.next;head1 = head1.next;}return returnHead;} }

上面的解法應(yīng)該是比較容易理解的。Google到網(wǎng)友還有另一種比較好的解法，可以只花額外的O(1)空間，使用同樣O(n)的時(shí)間。

這么做：

1. 在原來鏈表的每個(gè)節(jié)點(diǎn)后，插入一個(gè)一模一樣的復(fù)制節(jié)點(diǎn)。這樣copy的next順序就自然出來了。比如1-1'-2-2'-3-3'

2.?將每個(gè)復(fù)制的節(jié)點(diǎn)的random指向它前一個(gè)節(jié)點(diǎn)的random的下一個(gè)節(jié)點(diǎn)

3. 按next的順序抽出所有復(fù)制的節(jié)點(diǎn)，形成新的鏈表并返回。

代碼如下

/*** Definition for singly-linked list with a random pointer.* class RandomListNode {* int label;* RandomListNode next, random;* RandomListNode(int x) { this.label = x; }* };*/ public class Solution {public RandomListNode copyRandomList(RandomListNode head) {if (head == null) {return head;}RandomListNode returnHead = head;//在原鏈表的每個(gè)節(jié)點(diǎn)后都插入一個(gè)新節(jié)點(diǎn)while(head != null) {RandomListNode newNode = new RandomListNode(head.label);newNode.next = head.next;head.next = newNode;head = head.next.next;}//將每個(gè)復(fù)制的節(jié)點(diǎn)的random指向它前一個(gè)節(jié)點(diǎn)的random的nexthead = returnHead;while(head != null) {if(head.random != null) {head.next.random = head.random.next;}head = head.next.next;}//抽出每個(gè)復(fù)制的節(jié)點(diǎn)，返回head = returnHead;returnHead = returnHead.next;while(head != null) {RandomListNode newNode = head.next;head.next = head.next.next;//這個(gè)邊界條件一定要注意，否則原鏈表只有一個(gè)節(jié)點(diǎn)的時(shí)候會(huì)越界if(newNode.next != null) {newNode.next = newNode.next.next;}head = head.next;}return returnHead;} }

可以看出，上面的思想，同樣是要用某種方法在新復(fù)制的鏈表里找到每個(gè)節(jié)點(diǎn)的random節(jié)點(diǎn)，方法依然是要依賴于原鏈表。但是思路非常巧妙，值得體會(huì)。

轉(zhuǎn)載于:https://www.cnblogs.com/NickyYe/p/4379237.html

總結(jié)

以上是生活随笔為你收集整理的Copy List with Random Pointer的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。