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

反转链表【基础算法精讲 06】

视频地址

反转链表【基础算法精讲 06】_哔哩哔哩_bilibili

概念

链表的每一个结点都包含节点值 和1指向下一个结点的next指针 , 链表的最后一个结点指向空;

206 . 反转链表

用cur记录当前遍历到的结点 , 用pre表示下一个结点 , 用nxt表示cur的下一个结点,先将cur->next修改成pre,然后把pre 更新 成cur ,cur 更新 成nxt  ;

代码如下 : 

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* pre = nullptr;ListNode* cur = head ;while(cur != nullptr){ListNode* nxt = cur->next ;cur->next = pre ;pre = cur ;cur = nxt;}return pre ;}
};

92 . 反转链表II

这一题只需要反转[l,r]的部分结点

将反转链表的前一个结点成为p0 ;

然后和上一题一样反转链表 ;

也就是 : 

把p0的next指针指向cur,p0指向pre

有一个特殊的情况,当l = 1 的时候 , 没有p0 , 可以在前面加上一个哨兵结点为p0 ;

代码如下 : 

class Solution {
public:ListNode* reverseBetween(ListNode* head, int left, int right) {ListNode* dmy = new ListNode(0,head) ;ListNode* p0 = dmy ;for(int i=0;i<left-1;i++){p0 = p0 -> next ;}ListNode* pre = nullptr ;ListNode* cur = p0->next ;for(int i=1;i<=right-left+1;i++){ListNode* nxt = cur->next ;cur->next = pre ;pre = cur ;cur = nxt ;}p0->next->next = cur ;p0->next = pre ;return dmy->next ;}
};

25 . K个一组反转链表

先把链表的长度求出来 ;

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {int n = 0 ;ListNode* cur = head ;while(cur!=nullptr){ // 拿到链表的长度 n++;cur = cur->next ;}ListNode* dmy = new ListNode(0,head) ;ListNode* p0 = dmy ;while(n>=k){n-=k;ListNode* pre = nullptr;ListNode* cur = p0->next ;for(int i=0;i<k;i++){ListNode* nxt = cur->next;cur->next = pre ;pre = cur ;cur = nxt ;}ListNode* tmp = p0->next ;p0->next->next = cur ;p0->next = pre ;p0 = tmp ;}return dmy -> next;}
};

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

相关文章:

  • Git 初学
  • 智胜未来,新时代IT技术人风口攻略-第四版(弃稿)
  • 渗透专用虚拟机(公开版)
  • HCIA-HarmonyOS设备开发认证V2.0-3.2.轻量系统内核基础-时间管理
  • 嵌入式培训机构四个月实训课程笔记(完整版)-Linux ARM驱动编程第五天-ARM Linux编程之file_operations详解 (物联技术666)
  • 第9章 网络编程
  • Python setattr函数
  • [C#]winform制作仪表盘好用的表盘控件和使用方法
  • 探索弗洛姆的思想:人类本质与爱的哲学
  • 【碎片知识点】安装Linux系统 VMware与kali
  • Android 车载应用开发之SystemUI 详解
  • C# CAD-Xdata数据 添加(一)
  • 【NLP】MHA、MQA、GQA机制的区别
  • nginx upstream server主动健康监测模块添加https检测功能
  • OCP的operator——(4)用户任务:使用Operator创建etcd集群
  • win7自带截图工具保存失效解决办法
  • Android14之Android Rust模块编译语法(一百八十七)
  • 分布式文件系统 SpringBoot+FastDFS+Vue.js【三】
  • 【深度学习每日小知识】全景分割
  • 机器人能否返回原点
  • Mysql5.6忘记密码,如何找回(windows)
  • 算法训练营day29, 贪心算法3
  • 164基于matlab的奇异值分解、小波降噪、zoom细化
  • 每日OJ题_算法_递归③力扣206. 反转链表
  • 【Linux】指令 【whereis】
  • 牛客网SQL进阶128:未完成试卷数大于1的有效用户
  • GitHub的使用操作
  • 智慧公厕管理软件
  • 【30秒看懂大数据】数据中台
  • 【UI自动化测试技术】自动化测试研究:Python+Selenium+Pytest+Allure,详解UI自动化测试,了解元素交互的常用方法(精)(三)