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

糖逗

题目描述：

1. 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
   
2. 
   
3.  
   
4. 
   
5. 示例 1：
   
6. 
   
7. 
   
8. 
   
9. 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
   
10. 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
    
11. 示例 2：
    
12. 
    
13. 
    
14. 
    
15. 输入：head = [[1,1],[2,1]]
    
16. 输出：[[1,1],[2,1]]
    
17. 示例 3：
    
18. 
    
19. 
    
20. 
    
21. 输入：head = [[3,null],[3,0],[3,null]]
    
22. 输出：[[3,null],[3,0],[3,null]]
    
23. 示例 4：
    
24. 
    
25. 输入：head = []
    
26. 输出：[]
    
27. 解释：给定的链表为空（空指针），因此返回 null。
    
28.  
    
29. 
    
30. 提示：
    
31. 
    
32. -10000 <= Node.val <= 10000
    
33. Node.random&#160;为空（null）或指向链表中的节点。
    
34. 节点数目不超过 1000 。
    
35. &#160;
    
36. 
    
37. 来源：力扣（LeetCode）
    
38. 链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
    
39. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. /*
   
2. // Definition for a Node.
   
3. class Node {
   
4. public:
   
5.     int val;
   
6.     Node* next;
   
7.     Node* random;
   
8.    
   
9.     Node(int _val) {
   
10.         val = _val;
    
11.         next = NULL;
    
12.         random = NULL;
    
13.     }
    
14. };
    
15. */
    
16. class Solution {
    
17. public:
    
18.     Node* copyRandomList(Node* head) {
    
19.         if(head == NULL) return head;
    
20.         Node* temp1 = head;
    
21.         while(temp1){
    
22.             Node* new_node = new Node(temp1 -> val);
    
23.             Node* store = temp1 -> next;
    
24.             temp1 -> next = new_node;
    
25.             new_node -> next = store;
    
26.             temp1 = store;
    
27.         }
    
28.         temp1 = head;
    
29.         while(temp1){
    
30.             Node* temp2 = temp1 -> next;
    
31.             if(temp1 -> random){
    
32.                 temp2-> random = temp1 ->random -> next;
    
33.             }
    
34.             else{
    
35.                 temp2 -> random = NULL;
    
36.             }
    
37.             temp1 = temp2 -> next;
    
38.         }
    
39. 
    
40.         Node* old = head;
    
41.         Node* res = head -> next;
    
42.         Node* new_head = head -> next;
    
43.         while(new_head->next && new_head){
    
44.             Node* old1 = new_head -> next;
    
45.             Node* new1 = old1 -> next;
    
46.             old -> next = old1;
    
47.             new_head -> next = new1;
    
48.             old = old1;
    
49.             new_head = new1;
    
50.         }
    
51.         if(old)
    
52.             old->next=nullptr;
    
53.         return res;
    
54. 
    
55.         
    
56.     }
    
57. };

复制代码

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