思路分析
首先遍历两次是不行的,因为第二次遍历并不能知道第一次遍历的信息.
其实如果是普通链表的复制是非常简单的,只需要遍历一次原来的链表,每次都新建一个节点,然后将原来节点的值复制给新节点即可.
但是现在的问题在于有这个random指针,这个就是最大的问题.
哈希表
使用哈希表的方法只需要遍历两次即可.
第一次,将值进行复制
第二次,复制对应的next和random
复杂度分析:
时间复杂度:O(N),两轮哈希表遍历
空间复杂度: O(N),哈希表使用线性大小的额外空间
cpp
/*
// 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) {
unordered_map<Node*,Node*> pos;
pos[NULL] = NULL;
for(auto p=head;p;p=p->next){
pos[p] = new Node(p->val);
}
for(auto p=head;p;p=p->next){
pos[p]->next = pos[p->next];
pos[p]->random = pos[p->random];
}
return pos[head];
}
};
python
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
pos = {}
pos[None] = None
p = head
while p:
pos[p] = Node(p.val)
p = p.next
p = head
while p:
pos[p].next = pos[p.next]
pos[p].random = pos[p.random]
p = p.next
return pos[head]
拼接+拆分
这里不使用哈希表来作映射,而是使用链表拼接的方式来做映射.
考虑构建
原节点1->新节点1->原节点2->新节点2->原节点3->新节点3->....
的拼接链表,如此便可在访问原节点的random指向节点的同时找到新对应节点的random指向节点.
cpp
/**
* Definition for singly-linked list with a random pointer.
* struct ListNode {
* int val;
* ListNode *next, *random;
* ListNode(int x) : val(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
ListNode *copyRandomList(ListNode *head) {
for(auto p=head;p;p=p->next->next){
auto q = new ListNode(p->val);
auto ne = p->next;
p->next = q;
q->next = ne;
}
for(auto p=head;p;p=p->next->next)
if(p->random)// 不然会报错
p->next->random = p->random->next;
auto dummy = new ListNode(-1);
auto cur = dummy;
for(auto p=head;p;p=p->next){
cur->next = p->next;
cur = cur->next;
p->next = p->next->next;
}
return dummy->next;
}
};
python
# Definition for singly-linked list with a random pointer.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
# self.random = None
class Solution(object):
def copyRandomList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
p = head
while p:
q = ListNode(p.val)
ne = p.next
p.next = q
q.next = ne
p = p.next.next
p=head
while p:
if p.random:
p.next.random = p.random.next
p = p.next.next
dummy = ListNode(-1)
cur = dummy
p = head
while p:
cur.next = p.next
cur = cur.next
p.next = p.next.next
p = p.next
return dummy.next