LeetCode刷题--点滴记录011

落日映苍穹つ 2023-09-28 09:58 72阅读 0赞

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

**要求**

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

**解题**

#### C++版本 ####

#include <iostream>
    using namespace std;
    #include <unordered_map>
    
    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 == nullptr) 
                return head;
            Node* cur = head;
            unordered_map<Node*, Node*> map;
            
            while (cur != nullptr) {
                  //  复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
                map[cur] = new Node(cur->val);
                cur = cur->next;
            }
            cur = head;
            
            while (cur != nullptr) {
                   // 构建新链表的 next 和 random 指向
                map[cur]->next = map[cur->next];
                map[cur]->random = map[cur->random];
                cur = cur->next;
            }
            
            return map[head];          // 返回新链表的头节点
        }
    };
    
    void test01()
    {
        
        Solution s;
        Node* node1 = new Node(7);
        Node* node2 = new Node(13);
        Node* node3 = new Node(11);
        Node* node4 = new Node(10);
        Node* node5 = new Node(1);
    
        node1->next = node2;
        node2->next = node3;
        node3->next = node4;
        node4->next = node5;
    
        node1->random = NULL;
        node2->random = node1;
        node3->random = node5;
        node4->random = node3;
        node5->random = node1;
    
        Node* copy = s.copyRandomList(node1);
        while(copy != NULL){
        
            if (copy->random != NULL)
            {
        
                cout << copy->val << " " << copy->random->val << " ";
            }
            else
                cout << copy->val << " ";
            copy = copy->next;
        }
        cout << endl;
    }
    
    int main()
    {
        
        test01();
    
        system("pause");
        return 0;
    }

![在这里插入图片描述][eb90288936594616861be0e8122e78fe.png_pic_center]

#### Python版本 ####

class Node:
        def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
            self.val = int(x)
            self.next = next
            self.random = random
            
    class Solution:
        def copyRandomList(self, head):
            if head==None: 
                return head
            dic = {
        }
            cur = head
            while cur: # 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
                dic[cur] = Node(cur.val) # 创建字典对，原始节点一定为key
                cur = cur.next
            cur = head 
            
            while cur: # 构建新节点的 next 和 random 指向
                dic[cur].next = dic.get(cur.next)
                dic[cur].random = dic.get(cur.random)
                cur = cur.next
            
            return dic[head] # 返回新链表的头节点
    
    def test01():
        solution = Solution()
        node = Node(7)
        node.next = Node(13)
        node.next.next = Node(11)
        node.next.next.next = Node(10)
        node.next.next.next.next = Node(1)
        
        node.random = None
        node.next.random = node
        node.next.next.random = node.next.next.next.next
        node.next.next.next.random = node.next.next
        node.next.next.next.next.random = node
        
        copy = solution.copyRandomList(node)
        while copy:
            if copy.random:
                print(copy.val,copy.random.val,end=' ')
            else:
                print(copy.val,end=' ')
            copy = copy.next
                
    if __name__=="__main__":
        test01()

![在这里插入图片描述][2cbc38031467484e80ee3561fb93782c.png_pic_center]

#### Java版本 ####

package com.hailei_01;
    
    import java.util.HashMap;
    import java.util.Map;
    
    public class copyRandomList {
        
        public static void main(String[] args) {
        
            Node node1 = new Node(7);
            Node node2 = new Node(13);
            Node node3 = new Node(11);
            Node node4 = new Node(10);
            Node node5 = new Node(1);
    
            node1.next = node2;
            node2.next = node3;
            node3.next = node4;
            node4.next = node5;
    
            node1.random = null;
            node2.random = node1;
            node3.random = node5;
            node4.random = node3;
            node5.random = node1;
    
            Node copy = copyRandomList(node1);
            while(copy != null)
            {
        
                if (copy.random != null)
                {
        
                    System.out.print(copy.val+" "+copy.random.val+" ");
                }
                else
                {
        
                    System.out.print(copy.val+" "+ null+" ");
                }
                copy = copy.next;
            }
        }
    
        public static class Node {
        
            int val;
            Node next, random;
            public Node(int val) {
        
                this.val = val;
                this.next = null;
                this.random = null;
            }
        }
    
        public static Node copyRandomList(Node head) {
        
            if(head == null) return null;
            Node cur = head;
            Map<Node, Node> map = new HashMap<>();
    
            while(cur != null) {
          // 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
                map.put(cur, new Node(cur.val));
                cur = cur.next;
            }
            cur = head;
    
            while(cur != null) {
          // 构建新链表的 next 和 random 指向
                map.get(cur).next = map.get(cur.next);
                map.get(cur).random = map.get(cur.random);
                cur = cur.next;
            }
    
            return map.get(head); // 返回新链表的头节点
        }
    }

![在这里插入图片描述][a17c28278a414515aa7c811ee0d072b3.png_pic_center]

**希望本文对大家有帮助，上文若有不妥之处，欢迎指正**

**分享决定高度，学习拉开差距**

[eb90288936594616861be0e8122e78fe.png_pic_center]: https://img-blog.csdnimg.cn/eb90288936594616861be0e8122e78fe.png#pic_center
[2cbc38031467484e80ee3561fb93782c.png_pic_center]: https://img-blog.csdnimg.cn/2cbc38031467484e80ee3561fb93782c.png#pic_center
[a17c28278a414515aa7c811ee0d072b3.png_pic_center]: https://img-blog.csdnimg.cn/a17c28278a414515aa7c811ee0d072b3.png#pic_center