preface

Okay, actually, I didn’t get this one. Look at the problem solution, have ideas, and then write code is still wrong. Finally, it was found that the number tail was not handled when splitting the generation copied list and copied list. When you write linked list problems, it seems that you often make the mistake of not handling the last node or the first node properly. Well, watch out next time. I’m a real dish…

1. Title Description

  • You are given a list of length N, and each node contains an additional random pointer, random, which can point to any node or empty node in the list.

  • Construct a deep copy of the list. The deep copy should consist of exactly N new nodes, with each new node set to the value of its corresponding 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 a replicated list should point to a node in the original list.

  • For example, if there are two nodes X and Y in the original linked list, where x. randdom –> Y. Then the corresponding two nodes x and y in the replication list also have x. randdom –> y.

  • Returns the head node of the replication list.

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

  • Val: an integer representing Node.val.

  • Random_index: the 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 accepts only the head of the original list as an argument.

  • Example:

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

If you can, it’s easy to see if you can see the problem description of Leetcode in more detail

Second, the problem solving

2.1 train of thought

  • For each node, place the replicated node after the replicated node
  • Fixed the random pointer because the random of the replicated node points to the replicated node
  • You also need to fix the next pointer. By splitting the copied list from the copied list, we have fixed the next pointer
  • Don’t forget to deal with one detail after splitting: the tail node of the replicated list is still attached to the tail node of the replicated list and needs to be disconnected

2.2 code

Git code address

/** * // Definition for a Node. * function Node(val, next, random) { * this.val = val; * this.next = next; * this.random = random; *}; */ ** * @param {Node} head * @return {Node} */ const copyRandomList = function(head) {// If (head === null) Return null // copy = head, copy = head, copy = head, copy = head While (cur) {// Copy copy = new Node(cur.val, cur.next, Cur. Random) // join cur.next = copy // Process the next node to be copied cur = copy. Next} // After copying, pointer to the first replicated node cur = head While (cur) {if(cur. Random) {if(cur. Random) {if(cur. Random) {if(cur. Random) { Cur.random = cur.random. Next} // Process the next replicated node cur = cur.next? cur.next.next : Cur.next} // cur points to the first copy node and starts to split copy = cur = head. Next = head.next. Next // Copy points to copy cur.next = cur.next. Next // Copy points to copy cur.next = cur.next Next = null return copy} head = head. Next cur = cur.next}Copy the code