leetcode.138.随机链表的复制

Bertha 。 2022-09-04 07:59 87阅读 0赞

# leetcode.138.随机链表的复制 #

Java解法：时间复杂度O(n)；

# 解法一： #

使用hash存储原结点和克隆结点的映射关系，通过映射关系处理克隆结点的random指针

空间复杂度O(n)

# 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; } } */
    
    class Solution { 
        public Node copyRandomList(Node head) { 
            if(head == null){ 
                return head;
            }
            // map方法，空间复杂度O(n)
            Node node = head;
            // 使用hash表存储旧结点和新结点的映射---key:旧节点，val:新节点
            Map<Node,Node> map = new HashMap<>();
            while(node != null){ 
                Node clone = new Node(node.val,null,null);
                map.put(node,clone);
                node = node.next;
            }
            //第二次遍历
            node = head;
            while(node != null){ 
                //根据key旧节点，找到val新节点，完善next指针
                map.get(node).next = map.get(node.next);
                //根据key旧节点，找到val新节点，完善random指针
                map.get(node).random = map.get(node.random);
                //遍历指针后移
                node = node.next;
            }
            //根据旧节点，找到新节点
            return map.get(head);        
        }
    }

# cpp代码 #

class Solution { 
    public:
        Node* copyRandomList(Node* head) { 
            unordered_map<Node*, Node*> link;
            Node* pNode = head;
            while (pNode != nullptr) { 
                link[pNode] = new Node(pNode->val);
                pNode = pNode->next;
            }
            pNode = head;
            while (pNode != nullptr) { 
                link[pNode]->next = link[pNode->next];
                link[pNode]->random = link[pNode->random];
                pNode = pNode->next;
            }
            return link[head];
        }
    };