Linked List

注意事项：

1. a.next = b。 b赋值给a的next，指向是从左到右，也就是a.next指向b
2. it = it.next记得移动指针
3. fake_node如果链首会改变，引入fake_node
4. 决定是while it还是it.next
5. 删除节点.next = None

Python代码：

LeetCode 138 Copy List with Random Pointer

def copyRandomList(self, head: 'Node') -> 'Node':
	fake_head = Node(0)
	it = head
	while it:
		new_node = Node(it.val)
		it.next, new_node.next = new_node, it.next
		it = it.next.next
	it = head
	while it:
		if it.random:
			it.next.random = it.random.next
		it = it.next.next
	it, it_new = head, fake_head
	while it:
		it_new.next = it.next
		it.next = it.next.next
		it, it_new = it.next, it_new.next
	return fake_head.next

算法分析：

时间复杂度为O(n)，空间复杂度O(1)。