35.md

复杂链表的复制

题目

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）。 下图是一个含有5个结点的复杂链表。图中实线箭头表示next指针，虚线箭头表示random指针。为简单起见，指向null的指针没有画出

示例

输入:{1,2,3,4,5,3,5,#,2,#}

输出:{1,2,3,4,5,3,5,#,2,#}

解析:

• 我们将链表分为两段，前半部分{1,2,3,4,5}为ListNode，后半部分{3,5,#,2,#}是随机指针域表示。
• 以上示例前半部分可以表示链表为的ListNode:1->2->3->4->5
• 后半部分，3，5，#，2，#分别的表示为1的位置指向3，2的位置指向5，3的位置指向null，4的位置指向2，5的位置指向null

思路

• 难点在于如何拷贝那个随机指针

hash

• 先忽略随机指针，搞出来一个单链表副本
• 把两个新旧链表对应位置的元素做一个映射备用
• 遍历映射，如果某个新节点对应的旧节点有随机指针
• 那么先找到旧节点随机指针指向的旧节点
• 再通过映射找到这个旧节点对应的新节点
• 替黄老爷接上这条腿！

实现

func Clone(head *RandomListNode) *RandomListNode {
	if head == nil {
		return nil
	}
	releationship := make(map[*RandomListNode]*RandomListNode)
	sentry := &RandomListNode{}
	pre := sentry
	cur := head
	for cur != nil {
		newOne := &RandomListNode{
			Label: cur.Label,
		}
		releationship[cur] = newOne
		pre.Next = newOne
		pre = pre.Next
		cur = cur.Next
	}
	for origin, newOne := range releationship {
		if origin.Random == nil {
			newOne.Random = nil
		} else {
			newOne.Random = releationship[origin.Random]
		}
	}
	return sentry.Next
}