This article is participating in Python Theme Month. See the link to the event for more details

Topic describes

This is 138 on LeetCode. Copy the list with random Pointers. Difficulty is medium.

Tag: hash table, linked list

Given a list of length n, each node contains an additional pointer random, which can point to any node or null node in the list.

Construct a deep copy of the list. The deep copy should consist of exactly n new nodes, each of which has the same value as the original node. The next and random Pointers of the new node should also point to the new node in the replicated list, so that these Pointers in the original and replicated lists represent the same list state. No pointer in the copied list should point to a node in the original list.

For example, if the original list has two nodes X and Y, where x. randam –> Y. Then the corresponding two nodes x and y in the replicated list also have x. randam –> y.

Returns the head node of the replicated list.

The linked list in the input/output is represented by a list of n nodes. Each node is represented by a [val, random_index] :

  • Val: an integer representing node. val.
  • Random_index: Index of the node to which the random pointer points (range 0 to n-1); Null if it does not point to any node.

Your code only accepts the head node of the original list as an argument.

 

Example 1:

Input: the head = [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]] output: [[7, null], [13, 0], [11, 4], [10, 2], [1, 0]]Copy the code

Example 2:

Input: head = [[1,1],[2,1]] output: [[1,1],[2,1]Copy the code

Example 3:

Input: the head = [[3, null], [3, 0], [3, null]] output: [[3, null], [3, 0], [3, null]]Copy the code

Example 4:

Input: head = [] Output: [] Explanation: The given list is null (null pointer), so null is returned.Copy the code

Tip:

  • 0 <= n <= 1000
  • -10000 <= Node.val <= 10000

Simulate + hash table

To copy a list without considering the random pointer, we only need to use two Pointers: one to traverse the original list and one to construct the new list (always pointing to the end of the new list). This step can be seen as “create node + build next pointer relationship”.

Now that we add a random pointer to this, we can break down the construction of the relationship between the next pointer and the random pointer:

  1. Don’t considerrandomPointer, just like the original list copy, creates a new node and constructs itnextAt the same time, the hash table is used to record the mapping between the original node and the new node.
  2. The original list and the new list are traversed simultaneously, for each node of the original listrandomThrough the “hash table” to find the corresponding newrandomNode, and constructed on the new listrandomRelationship.

Java code:

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> map = new HashMap<>();
        Node dummy = new Node(-1);
        Node tail = dummy, tmp = head;
        while(tmp ! =null) {
            Node node = new Node(tmp.val);
            map.put(tmp, node);
            tail.next = node;
            tail = tail.next;
            tmp = tmp.next;
        }
        tail = dummy.next;
        while(head ! =null) {
            if(head.random ! =null) tail.random = map.get(head.random);
            tail = tail.next;
            head = head.next;
        }
        returndummy.next; }}Copy the code

Python 3 code:

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        hashmap = dict()
        dummy = Node(-1)
        tail, tmp = dummy, head
        while tmp:
            node = Node(tmp.val)
            hashmap[tmp] = node
            tail.next = node
            tail = tail.next
            tmp = tmp.next
        tail = dummy.next
        while head:
            if head.random:
                tail.random = hashmap[head.random]
            tail = tail.next
            head = head.next
        return dummy.next
Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

Simulation (in situ algorithm)

Obviously the time complexity cannot be optimized, consider how to reduce the space (do not use “hash table”).

The purpose of using “hash table” is to realize the mapping relationship between the original node and the new node, and further to quickly find the location of a node random in the new linked list.

Then we can use the next of the original list to do a temporary transfer, so as to achieve the mapping.

Specifically, we can proceed as follows:

  1. Copy each node node of the original linked list and append it to the back of the original node;
  2. complete
    1 1     After the operation, the odd positions of the list represent the original list nodes, the even positions of the list represent the new list nodes, and each of the original nodesnextThe pointer executes the corresponding new node. At this point, we need to construct a new listrandomPointer relationship, you can uselink[i + 1].random = link[i].random.next.
    i i     Is the odd subscript, and the meaning isOf the new list noderandomPointer to the corresponding node of the old linked listrandomThe next value of the pointer;
  3. Split the list.

Java code:

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Node dummy = new Node(-1);
        dummy.next = head;
        while(head ! =null) {
            Node node = new Node(head.val);
            node.next = head.next;
            head.next = node;
            head = node.next;
        }
        head = dummy.next;
        while(head ! =null) {
            if(head.random ! =null) {
                head.next.random = head.random.next;
            }
            head = head.next.next;
        }
        head = dummy.next;
        Node ans = head.next;
        while(head ! =null) {
            Node tmp = head.next;
            if(head.next ! =null) head.next = head.next.next;
            head = tmp;
        }
        returnans; }}Copy the code

Python 3 code:

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return None
        dummy = Node(-1)
        dummy.next = head
        while head:
            node = Node(head.val)
            node.next = head.next
            head.next = node
            head = node.next
        head = dummy.next
        while head:
            if head.random:
                head.next.random = head.random.next
            head = head.next.next
        head = dummy.next
        ans = head.next
        while head:
            tmp = head.next
            if head.next:
                head.next = head.next.next
            head = tmp
        return ans
Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

The last

This is No.138 in our “Brush through LeetCode” series, which began on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some with locks, and we will first brush through all the questions without locks.

In this series of articles, in addition to explaining how to solve the problem, I’ll give you the most concise code possible. If the general solution is involved, the corresponding code template will be provided.

In order to facilitate the students to debug and submit the code on the computer, I set up a related warehouse: github.com/SharingSour…

In the repository address, you can see the solution to the series, the corresponding code to the series, the LeetCode link, and other preferred solutions to the series.