C++刷剑指offer(面试题35. 复杂链表的复制)【链表】

糖逗

题目描述：

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

 

示例 1：



输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：



输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：



输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 4：

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
 

提示：

-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000 。
 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head == NULL) return head;
        Node* temp1 = head;
        while(temp1){
            Node* new_node = new Node(temp1 -> val);
            Node* store = temp1 -> next;
            temp1 -> next = new_node;
            new_node -> next = store;
            temp1 = store;
        }
        temp1 = head;
        while(temp1){
            Node* temp2 = temp1 -> next;
            if(temp1 -> random){
                temp2-> random = temp1 ->random -> next;
            }
            else{
                temp2 -> random = NULL;
            }
            temp1 = temp2 -> next;
        }

        Node* old = head;
        Node* res = head -> next;
        Node* new_head = head -> next;
        while(new_head->next && new_head){
            Node* old1 = new_head -> next;
            Node* new1 = old1 -> next;
            old -> next = old1;
            new_head -> next = new1;
            old = old1;
            new_head = new1; 
        }
        if(old)
            old->next=nullptr;
        return res;

        
    }
};

注意事项：
1.大致思路如图1
2.if(old)
   old->next=nullptr;
这行代码保证以前的链的最后一个元素指向null指针