LC138 - 随机链表的复制

package LinkedList

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

// 时间复杂度: O(n), 空间复杂度: O(1)
func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }
    for cur := head; cur != nil; cur = cur.Next.Next {
        copyNode := new(Node)
        copyNode.Val = cur.Val
        copyNode.Next = cur.Next
        cur.Next = copyNode
    }
    for cur := head; cur != nil; cur = cur.Next.Next {
        copyNode := cur.Next
        if cur.Random != nil {
            copyNode.Random = cur.Random.Next
        } else {
            copyNode.Random = nil
        }
    }
    copyHead := head.Next
    for cur := head; cur != nil; cur = cur.Next {
        copyNode := cur.Next
        cur.Next = copyNode.Next
        if copyNode.Next != nil {
            copyNode.Next = copyNode.Next.Next
        } else {
            copyNode.Next = nil
        }
    }
    return copyHead
}