Copy a linked list with a random pointer

Copy a list with a random pointer and return the new list

The problem solving code

Answer:

  1. Copy each node in pairs to the next digit of the current node, for example, 1->2->3 = 1->1->2-> 3->3
  2. In this case, the random of each node points to the same node, but the copied node should point to the next bit of the copied node
  3. For example, 1->random = 2, 1′->random = 2′(the next bit of the copied node)
  4. Then split the linked list into two independent linked lists to complete the list copy.
var copyRandomList = function(head) {
  if(! head)return null;
  let p = head;
  let q;
  while (p) { // Copy in pairs
    q = new Node(p.val); // Copy the current node
    q.random = p.random; // join the same random pointer field
    q.next = p.next; // point the next node of p to the node we copied
    p.next = q; // Point the next node of the current node to the replication node to complete the replication as 1->1
    p = q.next // p takes a step back and continues the loop until the end of the list (because the correct position of the original list is q.next after being inserted into the replicate node)
  }
  p = head.next; // Reassign to the list head node
  while (p) { // Fix the random pointer field
    if (p.random) p.random = p.random.next; // The random of the copied node should be the next bit to be copied.p = (p.next? .next || p.next );// Take two steps because there are the same replication nodes. If next. Next does not exist, assign next directly
  }
  let newHead = head.next; // The first node of the new list
  p = head; // The first node of the original list
  while (p) { // Split the linked list
    q = p.next; // When first entered, q is set to the first node of the new list, i.e. the replication node.
    p.next = q.next; // The original list points to the next bit of the replicated node. If 1 -> 1 '-> 2 -> 2' = 1(p) -> 2(q.ext)
    if (p.next) q.next = p.next.next; // The new list points to the next bit of the old list. If 1 -> 1 '-> 2 -> 2' = 1 '(q) -> 2' (p.ext.next)
    p = p.next; // p step back and continue the loop until the list is empty.
  }
  return newHead; // Return the replication list
};
Copy the code