欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【Leetcode】138. Copy List with Random Pointer

程序员文章站 2022-05-23 21:47:42
...

题目地址:

https://leetcode.com/problems/copy-list-with-random-pointer/

给定一个链表,每个node不但指向下一个node,还指向另一个random node。要求deep copy一份这个链表。

法1:DFS。同copy二叉树是类似的,这里可以采用递归的办法。但与二叉树不同的是,二叉树没有环,而这个链表的random有可能会指向之前的node,所以这里需要用一个哈希表记录一下某个node有没有被copy过。如果有的话,直接返回那个之前copy的就行了。否则就new一个新的。代码如下:

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public Node copyRandomList(Node head) {
    	// 记录已经被copy过的node和它们对应的node,
    	// key是原链表的node,value是深拷贝出来的对应的node
        Map<Node, Node> map = new HashMap<>();
        // null直接copy为null
        map.put(null, null);
        return dfs(head, map);
    }
    // 返回深拷贝出来的与参数node相对应的node
    private Node dfs(Node node, Map<Node, Node> map) {
    	// 如果该node已经被拷贝过,那就直接get出来返回
        if (map.containsKey(node)) {
            return map.get(node);
        }
        // 否则说明没拷贝过,那就先拷贝一个出来
        map.put(node, new Node(node.val));
        // 将其next和random也拷贝出来,接上去
        map.get(node).next = dfs(node.next, map);
        map.get(node).random = dfs(node.random, map);
        // 返回这个新拷贝出来的node
        return map.get(node);
    }
}

class Node {
    int val;
    Node next;
    Node random;
    
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

时间O(n)O(n),空间O(n)O(n)

法2:BFS。模仿BFS一个图的方法来做,也是要用一个哈希表记录已经copy过的node和其对应的node,然后用一个队列来做BFS。遇到未copy过的node就new出来接上去,否则直接接上已经copy过的那个对应的node。代码如下:

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class Solution {
    public Node copyRandomList(Node head) {
    	// 判空
        if (head == null) {
            return null;
        }
        // 记录已经copy过的node及其对应的node。含义同上
        Map<Node, Node> map = new HashMap<>();
        // 先把head拷贝一份
        map.put(head, new Node(head.val));
        // 再开一个队列把head放进去,以便于BFS
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            // 如果cur的next不为null且cur的next没被copy过的话,就new一个出来,建立map中的关联,并入队
            if (cur.next != null && !map.containsKey(cur.next)) {
                map.put(cur.next, new Node(cur.next.val));
                queue.offer(cur.next);
            }
            // 把cur对应的node的next给连上去
            map.get(cur).next = map.get(cur.next);
            // 与上面的next类似,copy出random
            if (cur.random != null && !map.containsKey(cur.random)) {
                map.put(cur.random, new Node(cur.random.val));
                queue.offer(cur.random);
            }
            map.get(cur).random = map.get(cur.random);
        }
        
        return map.get(head);
    }
}

时间复杂度O(n)O(n),空间O(n)O(n)