剑指 Offer 35. 复杂链表的复制

https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/

此问题的难点是如果顺序复制，random 指针可能指向未创建的节点。

可以分两次复制，第一次先复制链表，第二次再连接上 random 指针。

在新链表中，为了找到 random 指针指的是谁，需要先访问旧链表找到 random 指针，且需要在新链表中找到对应的节点，如果每次寻找这个节点都要遍历整个链表，时间复杂度则会是 O(N)。

哈希表

使用哈希表记录旧节点到新节点的映射，这样可以快速找到新节点，而不用再遍历。用 O(N) 的空间换了 O(N) 的时间。

func copyRandomList(head *Node) *Node {
    m := make(map[*Node]*Node)

    dummyHead := new(Node)
    currOld := head
    prev := dummyHead

    // 遍历旧链表，复制并链接新链表的 Next 指针
    for currOld != nil {
        curr := &Node{currOld.Val, nil, nil}
        prev.Next = curr

        m[currOld] = curr

        prev = curr
        currOld = currOld.Next
    }

    // 再遍历旧链表，链接新链表的 Random 指针
    curr := head
    for curr != nil {
        m[curr].Random = m[curr.Random]
        curr = curr.Next
    }

    return dummyHead.Next
}

原地复制 + 拆分链表

可见一个关键是需要知道旧节点和新节点的映射关系。可以在复制链表时，直接把每个新节点接在对应旧节点的后面，变成 old -> new -> old -> new -> 这样的结构。只要顺序遍历这个链表，就知道了旧节点和新节点映射关系，设置完指针后再拆开即可。省去了哈希表的空间开销。

注意需要复原旧链表，而不能仅仅把新链表拆出来。

func copyRandomList(head *Node) *Node {
    if head == nil {
        return head
    }
    curr := head

    // 复制链表
    for curr != nil {
        next := curr.Next
        curr.Next = &Node{curr.Val, curr.Next, nil}
        curr.Next.Next = next

        curr = next
    }

    // 设置 random 指针，curr 是旧链表头
    curr = head
    for curr != nil {
        if curr.Random != nil {
            curr.Next.Random = curr.Random.Next  // 设置对应新节点 curr.Next 的 Random 指针
        } else {
            curr.Next.Random = nil
        }
        curr = curr.Next.Next                    // 每次前进两个节点，保证 curr 是旧节点
    }

    // 拆分链表
    newHead := head.Next
    curr = head
    for curr != nil {
        newNode := curr.Next
        curr.Next = curr.Next.Next            // 将 Next 链接回下一个旧节点

        if newNode.Next != nil {
            newNode.Next = newNode.Next.Next  // 链接新节点的 Next 指针
        }
        
        curr = curr.Next                      // 前进 curr 到下一个旧节点
    }
    return newHead
}