剑指 Offer 35. 复杂链表的复制
👉题目:请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next指针指向下一个节点，
还有一个 random 指针指向链表中的任意节点或者 null。👈
🌟普通链表
Node(int value) { val = value; next = NULL; }
🎄题目中定义的复杂链表
Node(int _val) { int val = _val; Node *next = NULL; Node *random = NULL; }
🌈难点:
random的复制, 因为新的链表对应的random不是相邻的节点, 是随机的节点, 因此将这种关系复制给新链表就不是一件很容易的事.
💡法一:暴力(保底法)
1.将链表节点和next复制(也就是上面普通链表的复制)
2.遍历旧的链表查看每个节点N对应的random指向的节点M,然后从旧链表的首部开始遍历, 看什么时候走几步能到M, 得到步数
3.根据步数在新链表里查找M* 节点, 并让节点 N* 指向 M*
👉注意: 找M*节点时, 不是按照值找的(a == b), 而是按照地址来找的(*a == *b), 因为在遇到真正的M之前可能会遇到与它值相同的节点, 所以按地址值查找
✨复杂度的分析 : 对于一个含有 N 个节点的链表, 由于定位每一个节点的 random 都需要从链表头节点开始经过 O(n)的时间复杂度才能找到, 因此这种方法的时间复杂度是 O(n^2)
Node* copyRandomList(Node* head) { if(head == nullptr) return nullptr; Node* cur = head; // cur相当于头节点的副本 Node* temp = nullptr; Node* res; res = temp; // 1. 复制各节点 while(cur != nullptr) { Node *ptmp = new Node(cur->val); ptmp->next = nullptr; temp->next = ptmp; temp = temp->next; cur = cur->next; } res = res->next; Node *ans = res; // 2. 遍历旧链表得到步数并进行复制 cur = head; while(cur != nullptr) { temp = cur.random; Node *pp = head; int count = 0; while(pp != nullptr && pp != temp) { pp = pp->next; count++; } pp = res; while(pp != nullptr && --count != 0) { pp = pp->next; } res->random = pp; cur = cur->next; res = res->next; } return res; // 返回新链表头节点 }
💡法二 : 哈希法(空间换时间)
优化 : 找链表的节点, 找这个行为可以用什么来优化
🎉没错就是哈希🎉
哈希可以进行很快的查找, 时间复杂度为 O(1)
体现了空间换时间
将旧链表的节点和新链表的节点插入到哈希表中得到对应关系 <N, N*>, 则通过N->random得到的节点M, 通过哈希就可以得到 M* , 岂不美哉.
✨复杂度的分析 : 相较于法一, 我们用空间换时间, 需要一个大小为 O(n)的哈希表, 等同于用 O(n)的空间将时间复杂度从 O(n^2)降低到 O(n)
Node* copyRandomList(Node* head) { if(head == nullptr) return nullptr; Node* cur = head; unordered_map<Node*, Node*> map; // 1. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射 while(cur != nullptr) { map[cur] = new Node(cur->val); cur = cur->next; } cur = head; // 2. 构建新链表的 next 和 random 指向 while(cur != nullptr) { map[cur]->next = map[cur->next]; map[cur]->random = map[cur->random]; cur = cur->next; } // 3. 返回新链表的头节点 return map[head]; }
💡法三 : 叠加复制 + 截取
🌈有辅助空间的写法, 那么就有 没有辅助空间的写法
一种巧妙但又不容易发现的方法, 也是需要我们去积累的方法叠加复制 + 截取
具体步骤是:
1.在每一个节点的后面加一个节点
2.复制新的指针的时候 next 正常前后连接
3.新节点的 random 根据前一个节点的random 得到并向后移动一个单位
具体如图所示:
✨复杂度的分析 : 相对前两种方法, 我们用空间复杂度和时间复杂度都是最优的, 时间上我们需要三次遍历, 第一次建立新的节点, 第二次复制random, 最后再删除奇数位上的节点即可, 空间上, 只需要一个新链表的节点的空间时间复杂度也为 O(n)
Node* copyRandomList(Node* head) { if(head == nullptr) return nullptr; Node* cur = head; // cur相当于头节点的副本 // 1. 复制各节点，并构建拼接链表 while(cur != nullptr) { Node* tmp = new Node(cur->val); tmp->next = cur->next; cur->next = tmp; cur = tmp->next; } // 2. 构建各新节点的 random 指向 cur = head; while(cur != nullptr) { if(cur->random != nullptr) cur->next->random = cur->random->next; cur = cur->next->next; } // 3. 拆分两链表 cur = head->next; Node* pre = head, *res = head->next; while(cur->next != nullptr) { pre->next = pre->next->next; cur->next = cur->next->next; pre = pre->next; cur = cur->next; } pre->next = nullptr; // 单独处理原链表尾节点 return res; // 返回新链表头节点 }
🏁总结 : 将复杂问题, 分为多个小问题, 一个一个进行解决, 首先是节点和next的复制, 比较容易, 但是刚开始会发现random的复制不是很容易, 这个时候你就应该想, 那种数据结构可以将查找的速率优化呢, 是二分和哈希, 然后你进行分析, 发现这里不具有二段性, 所以你使用哈希进行优化, 如此你得到了O(n)的时间复杂度, 但是无巧不成题, 你还是会再进行深究, 那么你会发现更深的结构, 那就是链表自身的结构, 链表的连接方法就产生了这种巧妙的方法拼接+拆分, 于是乎你再进行整改, 得到几乎很快的方法, 然后你将这道题完全解决, 🎉从此在算法界里又离蒟蒻远了那么一点点, 🌈离算法岗又近了那么一个点.
