Links

35.复杂链表的复制(无Swift用例)

题目

请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
示例 1:
1
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2:
2
输入:head = [[1,1],[2,1]]
输出:[[1,1],[2,1]]
示例 3:
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
注意:本题与主站 138 题相同:https://leetcode-cn.com/problems/copy-list-with-random-pointer/

分析

题解

func copyRandomList2(_ head: ComplexListNode) -> ComplexListNode? {
var p: ComplexListNode? = head
// A a B b C c D d
while let current = p {
let node = ComplexListNode(current.val)
node.next = current.next
p?.next = node
p = current.next?.next
}
// 处理 random
p = head
while let current = p {
let clone = current.next
clone?.random = current.random?.next
p = clone?.next
}
// 删除原来的节点
let result: ComplexListNode? = head.next
p = result
while let current = p {
p?.next = current.next?.next
p = p?.next
}
return result
}