Shulou(Shulou.com)05/31 Report--

This article will explain in detail how to copy random pointers in Linkedin. The content of the article is of high quality, so the editor shares it for you as a reference. I hope you will have a certain understanding of the relevant knowledge after reading this article.

Topic description

A linked list is given, and each node contains an additional random pointer that can point to any node or empty node in the linked list.

Returns a deep-copy linked list.

Algorithm analysis

The algorithm of deep copying a normal linked list is very simple, because each node has only one next pointer to the next node, which is generally a linear structure; but the node in the topic has a random pointer, which can point to any node in the linked list, or an empty node. So when creating a new linked list, consider whether the node pointed to by the random pointer has been created and whether it already exists in the new linked list.

1. Need to check duplicates, naturally think of the hash table (hash table), so every time a new node, the original linked list nodes and new nodes into the HashMap, with the original node as the key, the new node as the value, so that in the copy of the next pointer to the node, or random pointer to the node, you can find in O (1) time in the hash table has been copied and put into the new linked list of the new node. The time complexity of this algorithm is O (N), and the extra space complexity is O (N).

two。 Using a hash table is fine, but it takes up extra space for O (N), and it's best if you can use constant-level extra space. In method 1, the space is occupied by the newly built hash table HashMap. If the original node and the new node can be connected by other methods, and the corresponding node can be found in O (1) time, the hash table can not be used. Because the topic has been told that random pointers will only point to nodes in the linked list or empty nodes, for this feature, each time a new node is created, the new node is inserted behind the corresponding node in the old linked list, such as the old linked list 1 → 2-> 3 → 4. After traversing and inserting, it will become 1-> 1-> 2-> 2-> 2-> 3-3-> 4-> 4' During the second traversal, the random pointer in the new node points to the next of the node pointed to by the old node random pointer. If the random pointer of node 4 points to node 1 in the linked list 1-> 1 nodes-> 2 nodes-> 2 nodes-> 3 nodes-> 4-> 4', then let the random of node 4 next (4') point to the next (1') of node 1; finally, traverse the list and take out all the new nodes to form a new linked list. The time complexity of this algorithm is O (3N) = O (N), and the extra space complexity is O (1).

Reference program

On how to copy random pointers in Linkedin to share here, I hope the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.