138.md

138. Copy List with Random Pointer

Leetcode link

解题思路

题目要求我们对有两个指针的链表进行深拷贝，那么我们可以用三个 for 循环依次做以下三件事：

1. 对于每一个链表节点，创建一个新的节点，把旧节点的值给新节点，把新节点的 next 指向旧节点的下一个节点，把旧节点的 next 指向新节点
2. 对于每一个新节点，把新节点的 random 指针指向旧节点的 random 的 next（也就是旧节点的 random 指向的旧节点的新节点）
3. 对于每一个新节点，把 next 指针指向自己的 next->next （也就是旧节点的 next 指向的节点的新节点）

C++

class Solution {
 public:
  Node* copyRandomList(Node* head) {
    if (!head) {
      return NULL;
    }

    for (Node* node = head; node; node = node->next->next) {
      Node* newNode = new Node(node->val);
      newNode->next = node->next;
      node->next = newNode;
    }
    Node* headNode = head->next;
    for (Node* node = head; node; node = node->next->next) {
      Node* newNode = node->next;
      newNode->random = node->random == NULL ? NULL : node->random->next;
    }
    for (Node* node = head; node; node = node->next) {
      Node* newNode = node->next;
      node->next = newNode->next;
      newNode->next = node->next == NULL ? NULL : node->next->next;
    }
    return headNode;
  }
};

Javascript

var copyRandomList = function(head) {
    if (!head) {
    return null;
  }

  for (let node = head; node; node = node.next.next) {
    const newNode = new Node(node.val, node.next, null);
    node.next = newNode;
  }
  const headNode = head.next;
  for (let node = head; node; node = node.next.next) {
    const newNode = node.next;
    newNode.random = node.random === null ? null : node.random.next;
  }
  for (let node = head; node; node = node.next) {
    const newNode = node.next;
    node.next = newNode.next;
    newNode.next = node.next === null ? null : node.next.next;
  }
  return headNode;
};