# LeetCode 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.

输入：
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

1. 你必须返回给定头的拷贝作为对克隆列表的引用。

Note:

1. You must return the copy of the given head as a reference to the cloned list.

### 第一种方法：

Java：

class Solution {
if (head == null) return null;
HashMap<Node, Node> map = new HashMap<>();//借助hashMap
Node tmp;
} else {
}
cur.next = tmp;
} else {
}
}
cur = tmp;//即cur=cur.next，刷新新链表当前节点
}
}
}

Python3：

class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
map = {}
else:
cur.next = tmp
else:
cur = tmp
return newHead.next

### 第二种方法：

Java：

class Solution {
if (head == null) return null;
//复制节点 1->2->3 ==> 1->1->1->2->2->3->3
while (cur != null) {
Node next = cur.next;
Node tmp = new Node(cur.val);
cur.next = tmp;
tmp.next = next;
cur = next;
}
//复制随机指针
while (cur != null) {
//cur.next.random=>新节点的随机节点     cur.random.next=>原节点的随机节点的下一个节点
cur.next.random = cur.random == null ? null : cur.random.next;
cur = cur.next.next;//链表扩展一倍后肯定是偶数位链表，所以可以直接用cur.next.next
}
//分离节点
while (cur != null) {
Node tmp = cur.next;
cur.next = tmp.next;
cur = cur.next;
tmp.next = cur == null ? null : cur.next;
}
}
}

Python3：

class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
while cur:
next = cur.next
tmp = Node(val=cur.val, next=next, random=None)
cur.next = tmp
cur = next
while cur:
cur.next.random = cur.random.next if cur.random else None
cur = cur.next.next
while cur:
tmp = cur.next
cur.next = tmp.next
cur = cur.next
tmp.next = cur.next if cur else None
return newHead

|
1月前
|

LeetCode第24题两两交换链表中的节点

27 3
|
30天前
|

LeetCode第86题分隔链表

25 2
|
30天前
|

LeetCode第83题删除排序链表中的重复元素

26 2
|
1月前
|

LeetCode第23题合并 K 个升序链表

27 2
|
18天前
|
C++ 索引
leetcode 707.设计链表

24 1
|
30天前
|

LeetCode第92题反转链表 II

45 0
|
1月前
|

LeetCode第21题合并两个有序链表

24 0
|
1月前
|

LeetCode第19题删除链表的倒数第 N 个结点

23 0
|
1月前
|

LeetCode初级算法题：环形链表+排列硬币+合并两个有序数组java解法
LeetCode初级算法题：环形链表+排列硬币+合并两个有序数组java解法
43 0
|
1月前
|

LeetCode初级算法题：反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
LeetCode初级算法题：反转链表+统计N以内的素数+删除排序数组中的重复项Java详解
17 0