当前位置： 首页 > news >正文

hot100——第六周

news 2025/6/22 9:21:41

目录

合并两个有序链表

两数相加

删除链表的倒数第 N 个结点

两两交换链表中的节点

K 个一组翻转链表

随机链表的复制

排序链表

合并 K 个升序链表

合并两个有序链表

解法：模拟

创建带头链表：只要两个链表都不为空，进行比较：小的节点进行尾插，之后走到下一个节点后再比较...其中一个链表为空就尾插另一个链表剩余节点

解法：递归

因为本质都是比较节点值，可以写成递归

class Solution
{
public:ListNode *mergeTwoLists(ListNode *list1, ListNode *list2){// 递归if (list1 == nullptr || list2 == nullptr)return list1 == nullptr ? list2 : list1;if (list1->val < list2->val){list1->next = mergeTwoLists(list1->next, list2);return list1;}list2->next = mergeTwoLists(list1, list2->next);return list2;// ListNode* head=new ListNode(-1),*tail=head;// while(list1||list2)// {//     if((list1&&list2&&list1->val<list2->val) || (list1&&list2==nullptr))//     {//         tail->next=list1;//         tail=list1;//         list1=list1->next;//     }//     else//     {//         tail->next=list2;//         tail=list2;//         list2=list2->next;//     }// }// ListNode* ret=head->next;// delete head;// return ret;}
};

两数相加

解法：模拟

链表是逆序的，返回结果也要是逆序的，所以直接从左向右根据加法规则根据节点连接，注意进位的处理：如果最后无节点但有节点则要把进位节点给加上

解法：递归

思路1：创建节点

每一位相加的做法都是一样的，可以使用递归：当前位相加的值创建新节点node，下一个节点next就是下一位节点的相加...递归结束后返回当前节点node就把结果全部连接起来（也是要注意处理进位）

思路2：不用创建节点

每次修改l1节点前先判断是否为空，为空就与l2节点交换保证每次修改都不是空节点；（如果需要创建节点来保存进位则是在递归出口处处理）

class Solution
{
public:ListNode *rc(ListNode *l1, ListNode *l2, int tmp){if (l1 == nullptr && l2 == nullptr){return tmp == 0 ? nullptr : new ListNode(tmp);}if (l1){tmp += l1->val;}if (l2){tmp += l2->val;}// 保证每次都有节点可以修改就不用创建节点if (l1 == nullptr){swap(l1, l2);}l1->val = tmp % 10;l1->next = rc(l1 == nullptr ? nullptr : l1->next, l2 == nullptr ? nullptr : l2->next, tmp / 10);return l1;// ListNode*node=new ListNode(tmp%10);// node->next=rc(l1,l2,tmp/10);// return node;}ListNode *addTwoNumbers(ListNode *l1, ListNode *l2){return rc(l1, l2, 0);// 模拟// ListNode* head=nullptr,*tail=nullptr;// int tmp=0;// while(l1||l2||tmp)// {//     if(l1)//     {//         tmp+=l1->val;//         l1=l1->next;//     }//     if(l2)//     {//         tmp+=l2->val;//         l2=l2->next;//     }//     if(head==nullptr)//     {//         head=new ListNode(tmp%10);//         tail=head;//     }//     else//     {//         tail->next=new ListNode(tmp%10);//         tail=tail->next;//     }//     tmp/=10;// }// return head;}
};

删除链表的倒数第 N 个结点

思路1：模拟

遍历一遍统计链表个数，然后计算出删除节点的位置，再次遍历后走到该位置；（注意删除头节点的特殊处理）

思路2：快慢指针

先让right指针走n步，然后同时走剩余步数知道right走到链表倒数位置的节点；此时left的下一个节点就是待删除的节点（可能right走n步就到了结尾就说明删除的是头节点这点要特殊处理，如果不想处理特殊情况就设置哨兵位头节点）

class Solution
{
public:ListNode *removeNthFromEnd(ListNode *head, int n){ListNode *left = head, *right = head;while (n--){right = right->next;}while (right && right->next){left = left->next;right = right->next;}// 删除头节点if (right == nullptr){head = head->next;delete left;}else{ListNode *tmp = left->next;left->next = tmp->next;delete tmp;}return head;// 统计总个数计算删除节点位置// int cnt=0;// ListNode*head1=head;// while(head1)// {//     cnt++;//     head1=head1->next;// }// cnt-=n;// ListNode*cur=head,*prev=nullptr;// //cnt找删除链表节点// while(cnt--)// {//     prev=cur;//     cur=cur->next;// }// //删除头节点// if(cur==head)// {//     head=head->next;//     delete cur;// }// else// {//     prev->next=cur->next;//     delete cur;// }// return head;}
};

两两交换链表中的节点

解法1：模拟

创建带哨兵位头节点head1，tail收集交换后的节点，多定义指针表示当前节点cur，下一个节点net，还要保留从下一个位置开始交换的节点tmp，不然交换后就找不到了；然后就是节点next的改变，由于定义多指针谁先谁后都无所谓

解法2：递归

由于两两交换节点是重复的，可以使用递归来解决：主要要先保存后面的节点再继续节点之间的交换，否则先交换后找不到后面要递归的节点

class Solution
{
public:ListNode *swapPairs(ListNode *head){if (head == nullptr || head->next == nullptr)return head;// 要先保存后面的节点ListNode *tmp = head->next->next;ListNode *net = head->next;head->next->next = head;head->next = swapPairs(tmp);return net;// if(head==nullptr||head->next==nullptr) return head;// ListNode* head1=new ListNode(-1),*tail=head1,*cur=head;// // 1 -> 2 -> 3// while(cur&&cur->next)// {//     ListNode*net=cur->next,*tmp=net->next;//     tail->next=net;  //-1 -> 2//     net->next=cur;   //2 -> 1//     cur->next=tmp;   //1 -> 3//     tail=cur;//     cur=tmp;// }// ListNode* ret=head1->next;// delete head1;// return ret;}
};

K 个一组翻转链表

解法：模拟

每次取k个节点进行逆序（反转链表）完成后使用带哨兵位的头节点进行收集

class Solution
{
public:void reverse(ListNode *head, ListNode *tail){if (head == tail)return;reverse(head->next, tail);head->next->next = head;head->next = nullptr;}ListNode *reverseKGroup(ListNode *head, int k){ListNode *cur = head, *head1 = new ListNode(-1), *tail = head1;while (cur){int cnt = k;ListNode *head2 = cur, *prev = nullptr;while (cur && (cnt--)){prev = cur;cur = cur->next;}// 后面不用翻转了if (cur == nullptr && cnt != 0){tail->next = head2;break;}reverse(head2, prev);tail->next = prev;tail = head2;}ListNode *ret = head1->next;delete head1;return ret;}
};

随机链表的复制

解法1：哈希表

拷贝节点时把原节点与拷贝节点作映射，后面初始化新拷贝链表时random时就通过原节点的random找到新节点的random

解法2：模拟

拷贝链表的每一个节点并放在原链表节点的后面

拷贝链表的random就是原节点的random的下一个节点（理解为现实生活中通过兄弟女朋友的介绍她的闺蜜找到女朋友）

把拷贝节点从链表中取出来（并还原链表）

class Solution
{
public:Node *copyRandomList(Node *head){Node *cur = head;while (cur){Node *node = new Node(cur->val), *tmp = cur->next;// 复制节点连接到后面node->next = cur->next;cur->next = node;cur = tmp;}// 随机节点的连接cur = head;while (cur){if (cur->random == nullptr)cur->next->random = nullptr;elsecur->next->random = cur->random->next;cur = cur->next->next;}// 复制节点取出来cur = head;Node *ret = nullptr, *tail = nullptr;while (cur){Node *tmp = cur->next->next;if (ret == nullptr){ret = cur->next;tail = ret;}else{tail->next = cur->next;tail = tail->next;}// 修复原链表cur->next = tmp;cur = cur->next;}return ret;// Node* ret=nullptr,*tail=nullptr,*cur=head;// unordered_map<Node*,Node*> hash;// while(cur)// {//     if(ret==nullptr)//     {//         ret=new Node(cur->val);//         tail=ret;//         hash[cur]=tail;//     }//     else//     {//         tail->next=new Node(cur->val);//         tail=tail->next;//         tail->next=nullptr;//走到最后节点的next置空//         hash[cur]=tail;//     }//     cur=cur->next;// }// tail=ret,cur=head;// while(cur)// {//     if(cur->random==nullptr) tail->random=nullptr;//     else tail->random=hash[cur->random];//     cur=cur->next;//     tail=tail->next;// }// return ret;}
};

排序链表

解法：归并（递归）

找到中间节点，把链表分成两段；

每段链表又可以重新分成两段...直到链表为空或者剩下一个就停止递归（递归出口）；

两次递归（合并）后我们就得到两个有序链表，把它进行合并即可

解法2：归并（循环）

归并递归的本质是从最简单的1(0)个节点的两段链表进行合并，递归两次往上返回得到两段有序的，2个节点的链表，就可以再次合并成一个大的有序链表...

所有可以使用length变量表示开始时进行合并的两个链表的大小，最开始是1，后面是2...length*=2地递增；这样就用递归销毁栈，把空间复杂度优化为O(1)

class Solution
{
public:ListNode *MidNode(ListNode *head){if (head == nullptr || head->next == nullptr)return head;ListNode *slow = head, *fast = head, *prev = nullptr;while (fast && fast->next){prev = slow;slow = slow->next;fast = fast->next->next;}// 截断prev->next = nullptr;return slow;}ListNode *MergeList(ListNode *head1, ListNode *head2){ListNode tmp(-1);ListNode *tail = &tmp;while (head1 && head2){if (head1->val < head2->val){tail->next = head1;head1 = head1->next;}else{tail->next = head2;head2 = head2->next;}tail = tail->next;}tail->next = head1 == nullptr ? head2 : head1;return tmp.next;}ListNode *sortList(ListNode *head){if (head == nullptr || head->next == nullptr)return head;ListNode *mid = MidNode(head);// 递归后获取有序链表ListNode *head1 = sortList(head);ListNode *head2 = sortList(mid);// 合并有序链表（归并）return MergeList(head1, head2);}
};class Solution
{
public:ListNode *MergeList(ListNode *head1, ListNode *head2){ListNode tmp(-1);ListNode *tail = &tmp;while (head1 && head2){if (head1->val < head2->val){tail->next = head1;head1 = head1->next;}else{tail->next = head2;head2 = head2->next;}tail = tail->next;}tail->next = head1 == nullptr ? head2 : head1;return tmp.next;}ListNode *SplistNode(ListNode *&head, int length){if (head == nullptr)return nullptr;ListNode *tmp = head, *prev = nullptr;while (head != nullptr && (length--)){prev = head;head = head->next;}prev->next = nullptr;return tmp;}int GetSize(ListNode *cur){int cnt = 1;while (cur){cnt++;cur = cur->next;}return cnt;}ListNode *sortList(ListNode *head){int cnt = GetSize(head);int length = 1;ListNode tmp = ListNode(-1, head);while (length < cnt){// 初始值的更新ListNode *tmp_tail = &tmp;ListNode *cur = tmp.next;while (cur){// 分ListNode *head1 = SplistNode(cur, length);ListNode *head2 = SplistNode(cur, length);// 合ListNode *head3 = MergeList(head1, head2);// 找尾ListNode *tail = head3;while (tail->next)tail = tail->next;// 尾插tmp_tail->next = head3;tmp_tail = tail;}length *= 2;}return tmp.next;}
};

合并 K 个升序链表

解法1：小根堆

使用小根堆（自己写链表值的比较函数）先收集所有链表的头节点；

取堆顶节点，把下一个节点放入（空节点不进）；

解法2：归并-递归

数组分成两部分依次分别递归...知道剩下一个链表或者不存在就返回；

得到两个递归回来的链表，进行合并，向上返回

解法2：归并-迭代

两两归并，把新链表放在归并的前一个链表中；归并完成就四四归并...直到不能归并我们得到返回的答案保存在list[0]中；

以上操作使用变量step来控制数组那些位置的链表进行归并，具体看代码

class Solution
{
public:struct cmp{bool operator()(const ListNode *p1, const ListNode *p2){return p1->val > p2->val;}};ListNode *MergeTwoList(ListNode *head1, ListNode *head2){ListNode tmp(-1);ListNode *tail = &tmp;while (head1 && head2){if (head1->val < head2->val){tail->next = head1;head1 = head1->next;}else{tail->next = head2;head2 = head2->next;}tail = tail->next;}tail->next = head1 == nullptr ? head2 : head1;return tmp.next;}ListNode *MergeSort(vector<ListNode *> &lists, int left, int right){if (left >= right)return lists[left];ListNode *head1 = MergeSort(lists, left, (left + right) / 2);ListNode *head2 = MergeSort(lists, (left + right) / 2 + 1, right);// 合并return MergeTwoList(head1, head2);}ListNode *MergeSortIterate(vector<ListNode *> &lists, int n){int step = 1;while (step < n){for (int i = 0; i + step < n; i += step * 2){lists[i] = MergeTwoList(lists[i], lists[i + step]);}step *= 2;}return lists[0];}ListNode *mergeKLists(vector<ListNode *> &lists){// 迭代int n = lists.size();if (n == 0)return nullptr;return MergeSortIterate(lists, n);// 递归// int n=lists.size();// if(n==0) return nullptr;// return MergeList(lists,0,n-1);// 最小堆// priority_queue<ListNode*,vector<ListNode*>,cmp> q;// //存数据// for(auto& list:lists)// {//     if(list) q.push(list);// }// ListNode tmp(-1);// ListNode* tail=&tmp;// //取数据// while(!q.empty())// {//     ListNode* node=q.top();//     if(node->next) q.push(node->next);//     q.pop();//     tail->next=node;//     tail=tail->next;// }// return tmp.next;}
};

以上便是全部内容，有问题欢迎在评论区指正，更新观看！

http://www.lryc.cn/news/573250.html

相关文章：

  • MagnTek MT6816-ACD 一款基于各向异性磁阻（AMR）技术的磁性角度传感器 IC
  • wordpress外贸独立站常用留言表单插件 contact form 7
  • 探索 Oracle Database 23ai 中的 SQL 功能
  • 小程序右上角○关闭事件
  • 基于深度学习的侧信道分析（DLSCA）Python实现（带测试）
  • RNN工作原理和架构
  • `teleport` 传送 API 的使用：在 Vue 3 中的最佳实践
  • Thrift 服务端的完整示例
  • 【设计模式】4.代理模式
  • 分组交换比报文交换的传输时延更低
  • PHP语法基础篇(五)：流程控制
  • Occt几何内核快速入门
  • 力扣网C语言编程题：多数元素
  • OPENPPP2传输层控制算法剖析及漏洞修复对抗建议
  • 5.3 VSCode使用FFmpeg库
  • Git 使用手册：从入门到精通
  • 基于Qt的UDP主从服务器设计与实现
  • 【Linux第四章】gcc、makefile、git、GDB
  • 从需求到落地：充电桩APP开发的定制化流程与核心优势
  • 免费1000套编程教学视频资料视频(涉及Java、python、C C++、R语言、PHP C# HTML GO)
  • Python subprocess 模块详解
  • 60-Oracle 10046事件-实操
  • Java面试复习指南：JVM原理、并发编程与Spring框架
  • 微服务架构的适用
  • Zephyr 电源管理机制深度解析：从 Tickless Idle 到平台 Suspend 实践
  • 【设计模式】6.原型模式
  • 道德的阶梯：大语言模型在复杂道德困境中的价值权衡
  • 经典控制理论：线性化笔记
  • 开源无广告GIF 制作软件三模录制，教程 / 游戏 GIF 一键生成支持鼠标轨迹显示
  • Linux运维新人自用笔记（Ubuntu磁盘命名规则、新磁盘分区、主流文件系统类型、mkfs命令格式化文件系统、临时和永久挂载、挂载报错、dd指令）