描述
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.
分析
这道题有点技巧，拢共分三步：
- 第一步，给原链表每个节点复制一个拷贝，插入到原节点后面。
- 第二步，再次遍历链表，给复制出来的节点设置random指针。
- 第三步，再次遍历链表，把原链表的节点和复制出来的节点拆成两个链表。
代码
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
class (object):
def __init__(self, x):
self.label = x
self.next = None
self.random = None
class Solution(object):
def copyRandomList(self, head):
"""
:type head: RandomListNode
:rtype: RandomListNode
"""
if not head:
return head
cur = head
while cur:
node = RandomListNode(cur.label)
node.next = cur.next
cur.next = node
cur = node.next
cur = head
while cur:
if cur.random:
cur.next.random = cur.random.next
cur = cur.next.next
cur = head
new_head = cur.next
while cur and cur.next:
next = cur.next
cur.next = cur.next.next
cur = next
return new_head
|
近期评论