剑指offer35 复杂链表的复制

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

题意

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

解法

由于random节点的存在，导致random节点指向的节点可能还没有被new出来
因此无法通过一次遍历完成链表的构建
需要知道原节点对应的新节点是什么
需要建立起两者之间的映射关系
一个比较直观的办法是使用map
这样空间复杂度会达到O(N)，代码见解法一

更好的解法是在建立新的链表时，将新产生的节点拼接在原节点之后
建立完成后遍历新产生的链表，让random节点指向正确的位置（因为原节点的下一个节点就是新节点）
再通过将链表拆分，返回复制后的链表，代码见解法二

代码

Hashmap解法

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*, Node*> nodes;
        Node* ret = new Node(0);
        Node* now = ret, *Head = head;
        while(head != nullptr) {
            now -> next = new Node(head -> val);
            nodes[head] = now -> next;
            head = head -> next;
            now = now -> next;
        }
        now -> next = nullptr;
        now = ret -> next;
        head = Head;
        while(head != nullptr) {
            if (head -> random) {
                now -> random = nodes[head -> random];
            }
            now = now -> next;
            head = head -> next;
        }
        return ret -> next;
    }
};

拼接拆分解法

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;
        Node* ret = new Node(0), *now = ret;
        // 1. 复制各节点，并构建拼接链表
        while(head != nullptr) {
            Node* nxt = head -> next;
            now -> next = head;
            now = now -> next;
            now -> next = new Node(head -> val);
            now = now -> next;
            head = nxt;
        }
        // 2. 构建各新节点的 random 指向
        now = ret -> next;
        while(now != nullptr) {
            if (now -> random) {
                now -> next -> random = now -> random -> next;
            }
            now = now -> next -> next;
        }
        // 3. 拆分两链表
        Node* odd = ret -> next, *even = ret -> next -> next;
        now = even;
        while(even -> next != nullptr) {
            odd -> next = odd -> next -> next;
            even -> next = even -> next -> next;
            odd = odd -> next;
            even = even -> next;
        }
        odd -> next = nullptr;
        return now;

    }
};