35.M 复杂链表的复制

题目

https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]] 

示例 2：

输入：head = [[1,1],[2,1]] 
输出：[[1,1],[2,1]] 

示例 3：

输入：head = [[3,null],[3,0],[3,null]] 
输出：[[3,null],[3,0],[3,null]] 

示例 4：

输入：head = [] 
输出：[] 
解释：给定的链表为空（空指针），因此返回 null。

提示：

• -10000 <= Node.val <= 10000

• Node.random 为空（null）或指向链表中的节点。

• 节点数目不超过 1000 。

解题思路

方法一：使用map保存原节点和新节点的映射关系，然后再重新给新节点赋值next和rand指针。如果某个节点在老链表中指向节点N，那么新节点在新链表中应该指向N'。空间复杂度O(n)

方法二：先复制每个节点，然后把节点N'拼在N的后面，然后重新设置sibling指针，最后再拆分链表。空间复杂度O(1)

实现代码

type Node struct {
	Val int
	Next *Node
	Random *Node
}

func copyRandomList(head *Node) *Node {
	if head == nil {
		return nil
	}

	//复制链表节点，并插入原链表
	p := head
	for p != nil {
		cloned := &Node{Val: p.Val}
		cloned.Next = p.Next
		p.Next = cloned
		p = cloned.Next
	}

	//给复制出来的节点赋值Rand指针
	p = head
	for p != nil {
		if p.Random != nil {
			p.Next.Random = p.Random.Next
		}
		p = p.Next.Next
	}

	//拆分链表
	newHead := head.Next
	p = head
	p1 := newHead
	for p != nil {
		p.Next = p1.Next
		if p1.Next != nil {
			p1.Next = p1.Next.Next
		}
		p = p.Next
		p1 = p1.Next
	}

	return newHead
}