2014
11-19

# LeetCode-Copy List with Random Pointer[链表]

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

// LeetCode, Copy List with Random Pointer
// 两遍扫描，时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
for (RandomListNode* cur = head; cur != nullptr; ) {
RandomListNode* node = new RandomListNode(cur->label);
node->next = cur->next;
cur->next = node;
cur = node->next;
}

for (RandomListNode* cur = head; cur != nullptr; ) {
if (cur->random != NULL)
cur->next->random = cur->random->next;
cur = cur->next->next;
}

// 分拆两个单链表
RandomListNode dummy(-1);
for (RandomListNode* cur = head, *new_cur = &dummy;
cur != nullptr; ) {
new_cur->next = cur->next;
new_cur = new_cur->next;
cur->next = cur->next->next;
cur = cur->next;
}
return dummy.next;
}
};


Java代码:

# Definition for singly-linked list with a random pointer.
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution:
# @return a RandomListNode
# copy current node to next node
while h is not None:
n = h.next
copy = RandomListNode(h.label)
copy.next = n
h.next = copy
h = n

# copy the random pointer
while h is not None:
if h.random is None: h.next.random = None
else:
h.next.random = h.random.next
h = h.next.next

# separate the list
while h is not None:
last.next = h.next
h.next = h.next.next
h = h.next
last=last.next

return  newHead.next

1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

2. 这道题目的核心一句话是：取还是不取。
如果当前取，则index+1作为参数。如果当前不取，则任用index作为参数。

3. 为什么for循环找到的i一定是素数叻，而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak，而你每次取余都用的是原来的m，也就是n

4. 样例输出和程序输出不吻合，修改一下样例输出吧。我用的是VC编译器，会提示我的i和j变量重复定义