35. 复杂链表的复制

题目

复杂链表定义如下，除了有个next指针指向下一个节点之外，还有一个sibling指针指向链表中的任意节点或者nullptr，需要实现一个Clone函数赋值一个复杂链表：

type ComplexListNode struct {
		val     int
		next    *ComplexListNode
		sibling *ComplexListNode
}

解题思路

方法一：以空间换时间，用一个map保存原节点和新节点之间的映射关系<N, N'>，如果某个节点在原链表中指向S，那么在新链表中就应该指向S'。

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

实现代码

方法一：

// Clone 以空间换时间，保存<N, N'>的映射关系
func Clone(head *ComplexListNode) *ComplexListNode {
	if head == nil {
		return nil
	}

	m := make(map[*ComplexListNode]*ComplexListNode)
	p := head
	for p != nil {
		m[p] = &ComplexListNode{val: p.val}
		p = p.next
	}

	p = head
	for p != nil {
		m[p].next = m[p.next]
		m[p].sibling = m[p.sibling]
		p = p.next
	}

	return m[head]
}

方法二：

// CloneV2 先复制链表，然后原地保存，再赋值兄弟指针，最后拆分链表
func CloneV2(head *ComplexListNode) *ComplexListNode {
	if head == nil {
		return nil
	}

	// 拷贝原有节点，并串联到链表中
	cur := head
	for cur != nil {
		next := cur.next
		newP := &ComplexListNode{val: cur.val}
		cur.next = newP
		newP.next = next
		cur = next
	}

	// 赋值sibling
	cur = head
	for cur != nil {
		if cur.sibling != nil {
			cur.next.sibling = cur.sibling.next
		}
		cur = cur.next.next
	}

	// 拆分新老链表
	newHead := head.next
	cur = head
	clonedCur := cur.next
	for cur.next.next != nil {
		cur.next = cur.next.next
		clonedCur.next = cur.next.next
		cur = cur.next
		clonedCur = clonedCur.next
	}
	cur.next = nil

	return newHead
}