【题目】 一种特殊的链表节点类描述如下：
public class Node { public int value; public Node next; public
Node rand;
public Node(int data) { this.value = data; }
}
Node类中的value是节点值，next指针和正常单链表中next指针的意义
一 样，都指向下一个节点，rand指针是Node类中新增的指针，这个指
针可 能指向链表中的任意一个节点，也可能指向null。 给定一个由
Node节点类型组成的无环单链表的头节点head，请实现一个 函数完成
这个链表中所有结构的复制，并返回复制的新链表的头节点。
进阶：
不使用额外的数据结构，只用有限几个变量，且在时间复杂度为 O(N)
内完成原问题要实现的函数。
解题思路
原问题的思路
（1） 用哈希表的结构，将原链表的节点和它的拷贝节点以键值对形式放到哈希表中，即创建一个哈希表，它的<key, value>为<原节点,拷贝节点>
（2）通过哈希表的get方法，在拥有当前节点以后我们可以得到它的拷贝节点，同时，我们得到当前节点的next指针所指向的节点以后，可以得到next指针的拷贝节点。rand节点同理。
（3）把当前节点的拷贝节点的next指针，指向当前节点的next指针所指向的节点的拷贝节点，rand指针同理。
（4）循环遍历这个链表，重复第3步的操作，我们就可以完成对原链表中所有结构的复制。
- Java代码如下：
public static Node copyListWithRand1(Node head) {
HashMap<Node, Node> map = new HashMap<>();
Node cur = head;
while (cur != null) { //把所有节点和它对应的拷贝节点放到哈希表
map.put(cur, new Node(cur.value));
cur = cur.next;
}
cur = head;
while (cur != null) { // 从哈希表中取出当前节点A对应的拷贝节点A'
// 将A'的next指针指向A的next指针所指向的节点的拷贝节点，rand指针同理
map.get(cur).next = map.get(cur.next);
map.get(cur).rand = map.get(cur.rand);
cur = cur.next;
}
return map.get(head);
}
进阶问题的思路
其实我觉得我应该画个图，因为这个东西用语言表达起来特别费劲，但是我没有时间，所以就先这样吧。
（1）遍历原链表，使得让原链表每一个节点的next指针指向它的拷贝节点，它的拷贝节点的next指针指向原节点的next节点。拷贝时要注意顺序，先用一个临时节点存放原节点的next节点，然后原节点的next指针指向它的拷贝节点，再把拷贝节点的next指针指向这个临时节点。
（2）经过第1步以后，这个链表的结构变成了A -> A' -> B -> B' -> C -> C' -> ......但是原链表所有节点的rand指针没有发生变化。
这时，将拷贝节点的rand指针指向当前节点A的rand指针所指向的节点N的下一个节点N'，因为N'就是当前节点A的rand指针所指向的N的拷贝节点，即A'.rand -> A.rand.next，但是要注意，当前节点的rand节点可能指向null，所以在设置前先要进行判断。
（3）经过第2步以后，拷贝节点的rand指针都已经设置好了，就差把原节点和拷贝节点从这个大的链表分开了。很简单，当前节点的next的next指向的就是它原本的next节点，拷贝节点同理。
- Java代码如下：
public static Node copyListWithRand2(Node head) {
if (head == null) {
return null;
}
Node cur = head;
Node next;
// 将原链表的节点的next指针指向拷贝节点，拷贝节点的next指针指向原节点的next节点
while (cur != null) {
next = cur.next;
cur.next = new Node(cur.value);
cur.next.next = next;
cur = next;
}
cur = head;
Node curCopy;
// 设置拷贝节点的rand指针
while (cur != null) {
next = cur.next.next;
curCopy = cur.next;
curCopy.rand = cur.rand != null ? cur.rand.next : null;
cur = next;
}
Node res = head.next;
cur = head;
// 将两个链表分开
while (cur != null) {
next = cur.next.next;
curCopy = cur.next;
cur.next = next;
curCopy.next = next != null ? next.next : null;
cur = next;
}
return res;
}
网友评论