【数据结构与算法】剑指 Offer 35. 复杂链表的复制

简介: 1.将链表节点和next复制(也就是上面普通链表的复制)2.遍历旧的链表查看每个节点N对应的random指向的节点M,然后从旧链表的首部开始遍历, 看什么时候走几步能到M, 得到步数3.根据步数在新链表里查找M* 节点, 并让节点 N* 指向 M*

剑指 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)的时间复杂度, 但是无巧不成题, 你还是会再进行深究, 那么你会发现更深的结构, 那就是链表自身的结构, 链表的连接方法就产生了这种巧妙的方法拼接+拆分, 于是乎你再进行整改, 得到几乎很快的方法, 然后你将这道题完全解决, 🎉从此在算法界里又离蒟蒻远了那么一点点, 🌈离算法岗又近了那么一个点.


相关文章
|
12天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
30 5
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
62 4
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
2月前
|
存储 缓存 算法
经典算法之链表篇(三)
经典算法之链表篇(三)
|
1月前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
43 0
|
2月前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
24 0
|
2月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
52 0
|
7天前
|
算法
基于GA遗传算法的PID控制器参数优化matlab建模与仿真
本项目基于遗传算法(GA)优化PID控制器参数,通过空间状态方程构建控制对象,自定义GA的选择、交叉、变异过程,以提高PID控制性能。与使用通用GA工具箱相比,此方法更灵活、针对性强。MATLAB2022A环境下测试,展示了GA优化前后PID控制效果的显著差异。核心代码实现了遗传算法的迭代优化过程,最终通过适应度函数评估并选择了最优PID参数,显著提升了系统响应速度和稳定性。
|
5天前
|
算法
基于WOA鲸鱼优化的购售电收益与风险评估算法matlab仿真
本研究提出了一种基于鲸鱼优化算法(WOA)的购售电收益与风险评估算法。通过将售电公司购售电收益风险计算公式作为WOA的目标函数,经过迭代优化计算出最优购电策略。实验结果表明,在迭代次数超过10次后,风险价值收益优化值达到1715.1万元的最大值。WOA还确定了中长期市场、现货市场及可再生能源等不同市场的最优购电量,验证了算法的有效性。核心程序使用MATLAB2022a实现,通过多次迭代优化,实现了售电公司收益最大化和风险最小化的目标。