011.随机链表的复制

• 138.随机链表的复制

随机链表的复制

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Random *Node
 * }
 */
 
func copyRandomList(head *Node) *Node {
	var (
		cur = head
		res *Node
		node *Node
	)
 
	// A -> A' -> B -> B' -> nil
	for cur != nil {
		node = &Node{
			Val: cur.Val,
			Next: cur.Next,
		}
		if res == nil {
			res = node
		}
		cur.Next = node
		cur = node.Next
	}
 
	// 调整 Random
	cur = head
	for cur != nil {
		node = cur.Next
		if cur.Random != nil {
			node.Random = cur.Random.Next
		}
		cur = node.Next
	}
 
	// 分离 A 和 A'
	cur = head
	for cur != nil {
		node = cur.Next
		cur.Next = node.Next
		if cur.Next != nil {
			node.Next = cur.Next.Next
		}
		cur = cur.Next
	}
 
	return res
}