Leetcode 105 - Copy List with Random Pointer：https://www.lintcode.com/problem/copy-list-with-random-pointer/description
Problem
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.
Example 1:
Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}
Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.
Note:
- You must return the copy of the given head as a reference to the cloned list.
Solution1 - 暴力法
最简单暴力的方法：
很明显，链表分成两个部分，一个是指向下一个节点组成的next 域，另一个是 random域。
那么我们的复制操作可以分成两个部分：
- 复制next域：这个操作比较简单，我们从头开始依次遍历所有的结点即可。
- 复制random域：这个操作有点麻烦，由于指针是随机指向的，因此无法通过一次遍历来实现，这里我们采用暴力的方式， 对于每一个random域，我们需要查找它在新链表中指向元素的元素位置，因此我们需要遍历一次新链表（O(N)）。而分别处理所有的随机指针需要O(N)。
因此暴力法的时间复杂度为$O(N^2)$，空间复杂度为 O(1)。
/*
// Definition for a Node.
class Node {
public int val;
public Node next;
public Node random;
public Node() {}
public Node(int _val,Node _next,Node _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
public Node copyRandomList(Node head) {
if(head == null)
return null;
Node newHead = new Node(head.val, null, null);
Node curr1 = head.next;
Node curr2 = newHead;
// copy val and next field
while(curr1 != null){
Node node = new Node(curr1.val, null, null);
curr2.next = node;
curr1 = curr1.next;
curr2 = curr2.next;
}
// copy random field
curr1 = head;
curr2 = newHead;
while(curr1 != null){
Node random = curr1.random;
if(random != null){
int value = random.val;
Node node = newHead;
while(node != null){
if(node.val == value){
break;
}
node = node.next;
}
curr2.random = node;
}else
curr2.random = null;
curr1 = curr1.next;
curr2 = curr2.next;
}
return newHead;
}
}
Solution2 - 用Hashmap来存储新旧链表的节点对应关系
其实分析一下，就知道我们的暴力解法的性能缺陷在哪？
我们每次复制随机指针的时候，每次要找到新链表中与原来链表对应的那个节点时，都需要同步遍历一次新链表，这个过程是O(n)的。
因此，我们可以思考，有没有什么方法把这个寻找元素操作的时间复杂度降低到O(1)呢？
由于新旧链表中的节点是一一对应的，那么我们用空间换时间的方法，用一个hashmap来存储这个映射关系。
最终，时间复杂度为 O(n)，而空间复杂度也为 O(n)。
/*
// Definition for a Node.
class Node {
public int val;
public Node next;
public Node random;
public Node() {}
public Node(int _val,Node _next,Node _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
public Node copyRandomList(Node head) {
Node newHead = null;
Node curr1 = head;
Node curr2 = null;
HashMap<Integer, Node> map = new HashMap<Integer, Node>();
// copy val and next field
while(curr1 != null){
Node node = new Node(curr1.val, null, null);
map.put(curr1.val, node);
if(curr2 == null){
newHead = node;
curr2 = node;
}else{
curr2.next = node;
curr2 = curr2.next;
}
curr1 = curr1.next;
}
// copy random field
curr1 = head;
curr2 = newHead;
while(curr1 != null){
if(curr1.random != null){
int value = curr1.random.val;
curr2.random = map.get(value);
}else{
curr2.random = null;
}
curr1 = curr1.next;
curr2 = curr2.next;
}
return newHead;
}
}
Solution3 - 用next指针域关联新旧结点
在上面那种方法，我们用hashmap来存储新旧链表中结点的对应关系。因此，对于有N个节点的链表，就需要一个大小为O(N)的Hashmap的空间，以将时间复杂度从$O(N^2)$降到了$O(N)$。
那么有没有什么方法，能够将空间复杂度也降下来，在使用不用辅助空间的情况下实现O(N)的时间效率。
其实我们需要的就只是能够建立新节点与原节点之前的对应关系就可以了, 链表中的顺序非随机访问方式，能够很简单的通过简单的next指针域查找下一个节点，那么我们将新节点直接插入到原结点的后面，这样可以很方便的通过原来节点找到新节点。
因此我们算法的流程如下：
1.遍历一遍原始链表，复制结点N对应的N’，将其插入到结点N的后面，如下图所示
2.确定每个随机指针的指向，只需遍历一遍链表即可确定每个结点的随机指针的指向，得到如下图结构
3.再次遍历一遍，将原始链表和复制链表分开，奇数为原始链表，偶数为复制链表，得到如下图型
动画描述：
/*
// Definition for a Node.
class Node {
public int val;
public Node next;
public Node random;
public Node() {}
public Node(int _val,Node _next,Node _random) {
val = _val;
next = _next;
random = _random;
}
};
*/
class Solution {
public Node copyRandomList(Node head) {
if(head == null)
return null;
// copy val
Node curr = head;
while(curr != null){
Node copiedNode = new Node(curr.val, null, null);
Node tmp = curr.next;
curr.next = copiedNode;
copiedNode.next = tmp;
curr = tmp;
}
// copy random
Node curr2 = null;
curr = head;
while(curr != null && curr.next != null){
curr2 = curr.next;
if(curr.random != null){
curr2.random = curr.random.next;
}
curr = curr.next.next;
}
// restore the orginal linkedlist and generate the new linkedlist
Node newHead = head.next;
curr = head;
curr2 = newHead;
while(curr != null && curr2 !=null){
curr.next = curr2.next;
curr = curr.next;
if(curr !=null){
curr2.next = curr.next;
curr2 = curr2.next;
}
}
return newHead;
}
}
Reference
- 剑指Offer–026-复杂链表的复制 - https://blog.csdn.net/gatieme/article/details/51227939
- 「复制带随机指针的链表」的一个很巧妙解法 - https://cxyxiaowu.com/articles/2019/04/18/1555548110989.html