一、题目描述

JZ25 复杂链表的复制
题目大意：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头节点
注意审题：我们需要对链表进行深拷贝

二、算法1（哈希表）

解题思路

  1. 假如链表没有随机指针, 我们的拷贝方式很简单, 只要先创建一个哨兵节点, 然后遍历一下给定链表, 创建新节点, 并不断和上个节点连接
  2. 本题的难点就在于每个节点还有一个指向空或其它节点的指针, 一种比较直观的想法就是先把整条链表连起来, 然后再挨着改变指针, 因此我们可以用哈希表来存放指针的映射关系, 然后根据将随机指针指向原链表随机指针映射在新链表的位置
  3. 算法实现：首先创建一个哨兵节点, 遍历一次原链表, 先将除随机指针外的部分创建并连接, 同时用哈希表记录指针之间的映射, 最后遍历一次哈希表, 将随机指针指向对应的位置

代码实现（C++11）

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if(!pHead) return pHead;    // 为空则直接返回空
        unordered_map<RandomListNode*, RandomListNode*> mp;    // 创建哈希表

        RandomListNode* dummy = new RandomListNode(0);    // 哨兵节点

        RandomListNode *pre = dummy, *cur = pHead;    // 指向哨兵和链表头的指针

        while(cur){
            RandomListNode* clone = new RandomListNode(cur->label);    // 拷贝节点
            pre->next = clone;    // 与上个结点连接
            mp[cur] = clone;    // 记录映射关系
            pre = pre->next;    // 指针移动
            cur = cur->next;
        }

        for(auto& [key, value] : mp){    // 遍历哈希表
            value->random = key->random == NULL ? NULL : mp[key->random];
        }

        delete dummy;    // 释放哨兵节点空间
        return mp[pHead];
    }
};

时间复杂度：O(n), 遍历一次链表和哈希表的时间
空间复杂度：O(n), 哈希表使用的空间

三、算法2（链表拼接、拆分）

解题思路

  1. 此解法参考了大佬的做法, 主要思路是将原链表的结点对应的拷贝节点连在其后, 最后链表变成 原1 -> 拷1 -> 原2 -> 拷2 -> ... -> null 的形式
  2. 然后我们再逐步处理对应的随机指针, 使用双指针, 一个指针指向原链表的节点, 一个指向拷贝链表的节点, 那么就有 拷->random = 原->random->next (random不为空)
  3. 最后再用双指针将两条链表拆分即可, 此算法大大优化了空间复杂度, 十分优秀

图片说明

代码实现（C++11）

class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead) {
        if(!pHead) return pHead;    // 为空则返回
        RandomListNode* cur = pHead;
        while(cur){
            RandomListNode* tmp = new RandomListNode(cur->label);    // 拷贝节点
            tmp->next = cur->next;
            cur->next = tmp;
            cur = tmp->next;
        }

        RandomListNode *old = pHead, *clone = pHead->next, *ret = pHead->next;
        while(old){
            clone->random = old->random == NULL ? NULL : old->random->next;    // 处理拷贝节点的随机指针
            if(old->next) old = old->next->next;    // 注意特判空指针
            if(clone->next) clone = clone->next->next;
        }

        old = pHead, clone = pHead->next;
        while(old){    // 拆分链表
            if(old->next) old->next = old->next->next;
            if(clone->next) clone->next = clone->next->next;
            old = old->next;
            clone = clone->next;
        }

        return ret;
    }
};

时间复杂度：O(n), 遍历了三次链表
空间复杂度：O(1), 使用了常数个链表指针变量