Leetcode (Sword finger offer) - 35 Replication of complex linked list

Topic link ： Click to open the link

The main idea of the topic ： A little .

Their thinking ： Solution (2) analysis .

Related enterprises

• Bytes to beat
• Amazon （Amazon）
• Facebook
• Microsoft （Microsoft）
• Bloomberg （Bloomberg）
• Google （Google）
• Shopee
• VMware

AC Code

• Java

/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */

//  Solution (1)
class Solution {
    public Node copyRandomList(Node head) {
        Node node = head;
        Map<Node, Node> map = new HashMap<>();
        while (null != node) {
            map.put(node, new Node(node.val));
            node = node.next;
        }

        node = head;
        while (null != node) {
            Node tmp = map.get(node);
            tmp.next = map.get(node.next);
            tmp.random = map.get(node.random);
            node = node.next;
        }

        return map.get(head);
    }
}

//  Solution (2)
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        // 1.  Copy each node , And build a splicing linked list 
        while(cur != null) {
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = tmp.next;
        }
        // 2.  Build the of each new node  random  Point to 
        cur = head;
        while(cur != null) {
            if(cur.random != null)
                cur.next.random = cur.random.next;
            cur = cur.next.next;
        }
        // 3.  Split two linked lists 
        cur = head.next;
        Node pre = head, res = head.next;
        while(cur.next != null) {
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre = pre.next;
            cur = cur.next;
        }
        pre.next = null; //  Handle the original end node of the linked list separately 
        return res;      //  Return the new chain header node 
    }
}

• C++

//  Solution (1)
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        Node* cur = head;
        unordered_map<Node*, Node*> map;
        // 3.  Copy each node , And establish  “ Original node  ->  New node ”  Of  Map  mapping 
        while(cur != nullptr) {
            map[cur] = new Node(cur->val);
            cur = cur->next;
        }
        cur = head;
        // 4.  To build a new linked list  next  and  random  Point to 
        while(cur != nullptr) {
            map[cur]->next = map[cur->next];
            map[cur]->random = map[cur->random];
            cur = cur->next;
        }
        // 5.  Return the head node of the new linked list 
        return map[head];
    }
};

//  Solution (2)
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return nullptr;
        Node* cur = head;
        // 1.  Copy each node , And build a splicing linked list 
        while(cur != nullptr) {
            Node* tmp = new Node(cur->val);
            tmp->next = cur->next;
            cur->next = tmp;
            cur = tmp->next;
        }
        // 2.  Build the of each new node  random  Point to 
        cur = head;
        while(cur != nullptr) {
            if(cur->random != nullptr)
                cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        // 3.  Split two linked lists 
        cur = head->next;
        Node* pre = head, *res = head->next;
        while(cur->next != nullptr) {
            pre->next = pre->next->next;
            cur->next = cur->next->next;
            pre = pre->next;
            cur = cur->next;
        }
        pre->next = nullptr; //  Handle the original end node of the linked list separately 
        return res;      //  Return the new chain header node 
    }
};