北京口碑好的十大装修公司_成都市房产信息网_百度开户代理商_淘宝宝贝排名查询

题目：深度拷贝一个带随即指针的链表，要求新链表内的所有指针不应指向旧链表的节点。

示例1：

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

示例2：

输入： head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

解题思路：此处主要解决的是如何让新链表中的所有指针指向新复制的节点。此处有两种解法。

解法一：

1）遍历原始链表，并复制所有结点，将新复制的结点插入原节点后方；例如原链表为 A->B->C,复制的节点分别为A',B',C'，经过第一步后，原始链表将变为A->A'->B->B'->C->C'

2）再次遍历链表，处理random节点值。我们已知 复制节点与原节点关系为 X'=X.next，所以同理，X'.random=X.random.next， 注意：此处的前提条件是X.random 不能为null。

3）再次遍历链表，拆分原始链表和新链表，再返回新链表即可。

代码：

/*
// Definition for a Node.
class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}
}
*/class Solution {public Node copyRandomList(Node head) {if (head == null) {return null;}//遍历原始链表，并复制新节点X'，将X'接入X节点后方Node currect = head;while (currect != null) {Node copyNod = new Node(currect.val);copyNod.next = currect.next;currect.next = copyNod;currect = copyNod.next;}//再次遍历链表，处理random值，关系式为 X'.random=X.random.nextcurrect = head;while (currect != null) {if (currect.random != null) {currect.next.random = currect.random.next;}currect = currect.next.next;}//第三遍遍历链表，将链表拆分，奇数项节点为原始节点，偶数项系项节点为复制节点。Node newHead = head.next;Node newCur = newHead;currect = head;while (currect != null) {currect.next = newCur.next;currect = currect.next;if (currect != null) {newCur.next = currect.next;newCur = newCur.next;}}return newHead;}
}

解题思路二：使用hashmap

1）遍历链表，复制每一个节点并放入hashmap中

2）在hashmap中，遍历原始链表中的每一个节点的值，并对其的next和random值进行赋值

/*
// Definition for a Node.
class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}
}
*/class Solution {public Node copyRandomList(Node head) {if (head == null) {return null;}HashMap<Node, Node> map = new HashMap<>();//遍历原始链表，复制每一个节点，并将节点放入hashmap中Node currect = head;while (currect != null) {map.put(currect, new Node(currect.val));currect = currect.next;}//再次遍历链表，处理next和random指针currect = head;while (currect != null) {map.get(currect).next = map.get(currect.next);map.get(currect).random = map.get(currect.random);currect = currect.next;}return map.get(head);}
}