题解 | #复杂链表的复制#

写的很冗余

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
      if (pHead == nullptr) {
        return pHead;
      }
      
      //  智能指针头结点，防止内存泄漏
      auto head = std::make_unique<RandomListNode>(-1);
      RandomListNode *tar = head.get(), *obj = pHead;
      
      //  先构建基本链表
      while (obj) {
        tar->next = new RandomListNode(obj->label);
        obj = obj->next;
        tar = tar->next;
      }
      
      tar = head->next;
      obj = pHead;
      
      //  构建随机指向
      while (tar) {
        //  在随机赋值中已经完成或者随机域为空的跳过
        if (tar->random || obj->random == nullptr) {
          tar = tar->next;
          obj = obj->next;
          continue;
        }
        //  回溯位置
        RandomListNode *pre1 = tar;
        RandomListNode *pre2 = obj;
        //  找到随机指针指向的节点
        //  并且接替赋值
        while (tar->random == nullptr && obj->random) {
          //  有随机域查找并赋值
          int num = obj->random->label;
          RandomListNode *pre = tar;
          tar = head->next;
          obj = pHead;
          //  随机域可能出现在节点之前
          while (tar) {
            if (tar->label == num) {
              break;
            }
            obj = obj->next;
            tar = tar->next;
          }
          pre->random = tar;
        }
        tar = pre1->next;
        obj = pre2->next;
      }
      
      return head->next;
    }
};

哈希表改进

/*
struct RandomListNode {
    int label;
    struct RandomListNode *next, *random;
    RandomListNode(int x) :
            label(x), next(NULL), random(NULL) {
    }
};
*/
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
      if (pHead == nullptr) {
        return pHead;
      }
      
      auto head = std::make_unique<RandomListNode>(-1);
      std::unordered_map<int, RandomListNode *> hash;
      
      RandomListNode *clone = head.get(), *source = pHead;
      
      while (source) {
        clone->next = new RandomListNode(source->label);
        clone = clone->next;
        source = source->next;
        hash[clone->label] = clone;
      }
      
      clone = head->next;
      source = pHead;
      
      while (clone) {
        if (source->random) {
          clone->random = hash[source->random->label];
        }
        clone = clone->next;
        source = source->next;
      }
      
      return head->next;
    }
};

双指针过于冗长（暂不实现）