Leetcode138. Copy List with Random Pointer

题目描述

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Example 1:

1 2	Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

1 2	Input: head = [[1,1],[2,1]] Output: [[1,1],[2,1]]

Example 3:

1 2	Input: head = [[3,null],[3,0],[3,null]] Output: [[3,null],[3,0],[3,null]]

Example 4:

1
2
3

Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.

思路

先根据链表将Node的value存储使用map存储Node。

代码

/*
// 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;
        HashMap<Node,Node> map =new HashMap<>();
        Node temp0 = head;
        Node output = new Node(0);
        Node temp1 = output;
        while(temp0!=null){
            temp1.next = new Node(temp0.val);
            map.put(temp0,temp1.next);
            temp0 = temp0.next;
            temp1 = temp1.next;
        }
        temp1 = output.next;
        while(head!=null){
            Node random = head.random;
            if(random!=null){
                temp1.random = map.get(random);
            }
            head= head.next;
            temp1 = temp1.next;
        }
        return output.next;
    }
}