​LeetCode刷題實戰138:複製帶隨機指針的鍊表

算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！今天和大家聊的問題叫做 複製帶隨機指針的鍊表，我們先來看題面：https://leetcode-cn.com/problems/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.

 

題意給定一個鍊表，每個節點包含一個額外增加的隨機指針，該指針可以指向鍊表中的任何節點或空節點。我們用一個由 n 個節點組成的鍊表來表示輸入/輸出中的鍊表。每個節點用一個 [val, random_index] 表示：random_index：隨機指針指向的節點索引（範圍從 0 到 n-1）；如果不指向任何節點，則為  null 。

解題遍歷第一遍鍊表，我們不考慮鍊表之間的相互關係，僅僅生成所有節點，然後把它存到 HashMap 中，val 作為 key，Node 作為 value。遍歷第二遍鍊表，將之前生成的節點取出來，更新它們的 next 和 random 指針。

public Node copyRandomList(Node head) {
    if (head == null) {
        return null;
    }
    HashMap<Node, Node> map = new HashMap<>();
    Node h = head;
    while (h != null) {
        Node t = new Node(h.val);
        map.put(h, t);
        h = h.next;
    }
    h = head;
    while (h != null) {
        if (h.next != null) {
            map.get(h).next = map.get(h.next);
        }
        if (h.random != null) {
            map.get(h).random = map.get(h.random);
        }
        h = h.next;
    }
    return map.get(head);
}

好了，今天的文章就到這裡，如果覺得有所收穫，請順手點個在看或者轉發吧，你們的支持是我最大的動力。