Copy List with Random Pointer

题目介绍

LeetCode 138. Copy List with Random Pointer。

复杂度

时间复杂度: O(n), 空间复杂度: O(1)

解题思路

class Solution {
    func copyRandomList(_ head: Node?) -> Node? {
        if head == nil {
            return head
        }
        var node = head
        // 1. 将复制节点添加到原节点后面
        while node != nil {
            let copy = Node(node!.val)
            copy.next = node?.next
            node?.next = copy
            node = copy.next
        }
        // 2. 复制random节点
        node = head
        while node != nil {
            node?.next?.random = node?.random?.next
            node = node?.next?.next
        }
        // 3. 取出拷贝的链表
        node = head
        let newHead = head?.next
        var newNode = newHead
        while node != nil {
            node?.next = node?.next?.next
            newNode?.next = newNode?.next?.next
            node = node?.next
            newNode = newNode?.next
        }
        return newHead
    }
}

**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文首发于Ivan’s Blog | 叶帆的博客博客（ http://yeziahehe.com ），版权所有，侵权必究。

本文链接：http://yeziahehe.com/2020/04/03/CopyListWithRandomPointer/