LeetCode 138：复制带随机指针的链表 Copy List with Random Pointer

0
0
0
1. 云栖社区>
2. 博客>
3. 正文

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

+ 关注