LeetCode138. 复制带随机指针的链表🌟🌟中等
PS：这道题我之前讲解过，而且有字幕，就直接拿之前的视频了，风格都是一模一样的哈
课后作业
问题描述
原文链接：138. 复制带随机指针的链表
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示Node.val的整数。random_index：随机指针指向的节点索引（范围从0到n-1）；如果不指向任何节点，则为null。
你的代码只接受原链表的头节点 head 作为传入参数。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
提示：
0 <= n <= 1000-104 <= Node.val <= 104Node.random为null或指向链表中的节点。
代码实现
Java
/*
// 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;
}
// 复制链表节点
Node cur = head;
while(cur != null){
Node next = cur.next;
cur.next = new Node(cur.val);
cur.next.next = next;
cur = next;
}
// 复制随机节点
cur = head;
while(cur != null){
Node curNew = cur.next;
curNew.random = cur.random == null ? null : cur.random.next;
cur = cur.next.next;
}
// 拆分,比如把 A->A1->B->B1->C->C1拆分成 A->B->C和A1->B1->C1
Node headNew = head.next;
cur = head;
Node curNew = head.next;
while(cur != null){
cur.next = cur.next.next;
cur = cur.next;
curNew.next = cur == null ? null : cur.next;
curNew = curNew.next;
}
return headNew;
}
}
Python
# Definition for a Node.
class Node(object):
def __init__(self, x, next=None, random=None):
self.val = int(x)
self.next = next
self.random = random
class Solution(object):
def copyRandomList(self, head):
"""
:type head: Node
:rtype: Node
"""
if head is None:
return None
# 复制链表节点
cur = head
while cur is not None:
next = cur.next
cur.next = Node(cur.val)
cur.next.next = next
cur = next
# 复制随机节点
cur = head
while cur is not None:
curNew = cur.next
curNew.random = None if cur.random is None else cur.random.next
cur = cur.next.next
# 拆分,比如把 A->A1->B->B1->C->C1拆分成 A->B->C和A1->B1->C1
headNew = head.next
cur = head
curNew = head.next
while cur is not None:
cur.next = cur.next.next
cur = cur.next
curNew.next = None if cur is None else cur.next
curNew = curNew.next
return headNew
C++
/* Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};*/
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head == NULL){
return NULL;
}
// 复制链表节点
Node* cur = head;
while(cur != NULL){
Node* next = cur->next;
cur->next = new Node(cur->val);
cur->next->next = next;
cur = next;
}
// 复制随机节点
cur = head;
while(cur != NULL){
Node* curNew = cur->next;
curNew->random = cur->random == NULL ? NULL : cur->random->next;
cur = cur->next->next;
}
// 拆分,比如把 A->A1->B->B1->C->C1拆分成 A->B->C和A1->B1->C1
Node* headNew = head->next;
cur = head;
Node* curNew = head->next;
while(cur != NULL){
cur->next = cur->next->next;
cur = cur->next;
curNew->next = cur == NULL ? NULL : cur->next;
curNew = curNew->next;
}
return headNew;
}
};
Go
/**
* Definition for a Node.
* type Node struct {
* Val int
* Next *Node
* Random *Node
* }
*/
func copyRandomList(head *Node) *Node {
if head == nil {
return nil
}
// 复制链表节点
cur := head
for cur != nil {
next := cur.Next
cur.Next = &Node{Val: cur.Val}
cur.Next.Next = next
cur = next
}
// 复制随机节点
cur = head
for cur != nil {
curNew := cur.Next
if cur.Random != nil {
curNew.Random = cur.Random.Next
}
cur = cur.Next.Next
}
// 拆分,比如把 A->A1->B->B1->C->C1拆分成 A->B->C和A1->B1->C1
headNew := head.Next
cur = head
curNew := head.Next
for cur != nil {
cur.Next = cur.Next.Next
cur = cur.Next
if curNew.Next != nil {
curNew.Next = curNew.Next.Next
}
curNew = curNew.Next
}
return headNew
}