算法复习:链表

链表定义

struct ListNode { 
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

链表的遍历ListNode p=head; while(p!=null) p=p.next; 

找到链表的尾结点p=head; while(p.next!=null)p=p.next;

链表节点的个数

          p=head; cnt=0; //cnt与p不同步对应

          while(p!=null):cnt++; p=p.next

          cnt与p不同步对应的原因:

          while停止后,p为null,cnt为对应到最后一个节点上面

         规律:开始的时候同步和结束时候的同步规律是一致的。

链表删除

 注意:1.删除节点需要dummyNode  2.最后返回的是dummyNode.next而不是head.

       因为head可能被删掉

 ListNode dummyNode=new ListNode();

   dummyNode.next=head;

   (p.next为待删除节点)

    p.next=p.next.next;

   return dummyNode.next;

ListNode* deleteNode(ListNode* head, ListNode* p) {
        // 创建一个虚拟头节点,便于处理链表头部的删除操作
        ListNode dummyNode(0);
        dummyNode.next = head;
        // 将虚拟头节点的下一个节点指向原链表头节点
        ListNode* prev = &dummyNode;
        // 遍历链表,找到待删除节点的前驱节点
        while (prev->next&& prev->next != p) {
            prev = prev->next;
        }
        // 如果待删除节点存在,则进行删除操作
        if (prev->next) {
            prev->next = prev->next->next;
        } 
        else {
            std::cout << "Target node not found in the list." << std::endl;
        }
        // 返回处理后的新链表头节点(即原链表头节点)
        return dummyNode.next;
}

链表插入

  (1)头插法: dummyNode,p:

p.next=dummyNode.next;
dummyNode.next=p;

  (2)尾插法

tail,p:
   tail.next=p; tail=p;

   在尾插法的过程中,tail.next不需要清空:

   每次插入时tail.next都会重定向到待插入的节点

   最后tail.next=null

找到链表的第index个节点

int i=1;
p=head;
//计数变量和p索引始终同步对应:while停止后,i对应p.
while(i<index&&p!=null)
     p=p.next;
     i++;

链表翻转 dummyNode + 头插法

   ListNode dummyNode=new ListNode();
   dummyNode.next=null;
   ListNode p=head;
   if(head==null)return null;
   ListNode q=p.next;
   while(p!=null)
       q=p.next;
       p.next=dummyNode.next;
       dummyNode.next=p;
       p=q;
   return dummyNode.next;
两个链表第一个公共的节点

 (1)求两个链表长度n1,n2  

 (2)长的链表走|n1-n2|步,使两个链表长度相同

 (3)两个链表一起走,相等返回,走到头返回null

倒数第k个节点

(1) 求节点个数n

(2)求第n-k+1个节点

删除重复节点

 (1)增加虚拟头结点

   (2)链表节点的删除

     p.next=p.next.next

删除链表倒数第n个节点

   (1)添加虚拟头结点

   (2)求链表长度l

   (3)找第l-n的节点并删除

判断环

         如果有环:slow和fast走一定会相遇

         如果没有环:在有限次遍历链表后,一定为空

if head==null:return false//特判
slow=head;
fast=head.next;   
while(slow!=fast&&slow!=null&&slow.next!=null&&fast!=null&&fast.next!=null)
       slow=slow.next;
       fast=fast.next.next;
       if(slow==fast)return true;
       return false 
判断环的入口

(1)fast和slow置头结点,速度为2,1

(2)相遇后fast置头结点,速度为1

(3)fast和slow相遇的节点是入口

fast=pHead;
slow=pHead;
while(fast!=null&&fast.next!=null){
     fast=fast.next.next;slow=slow.next;
     if(fast==slow){
          fast=pHead;
          while(fast!=slow){
              fast=fast.next;
              slow=slow.next;}
          return fast;
return nullptr//如果遍历到空节点,说明没有环,返回null
合并两个排序的链表
p=head1,q=head2;
tail = dummyNode;
while(p!=null&&q!=null){
     if(p.val<q.val)tail.next=p;tail=p;p=p.next;
     else  tail.next=q;tail=q;q=q.next;
}

tail直接指向非空的一个链表,如果两个链表都是空,那么就指向空
tail.next=(p==null)?q:p;
return dummyNode.next;
回文链表

存储链表的值

指定区间反转链表

思路:切断后反转局部链表后重接回去。node1,node2,..,p,start,...end,q...noden

需要找到p,q,start,end

 (1)把区间的链表单独拎出来:

 p.next=null; end.next=null;

 (2)反转区间reverse

 (3)重写接回去

  reverse(start);

增加虚拟头结点:

  如果说从第一个开始就翻转,那么就得分情况讨论,所以要添加一个虚拟头结点。

奇偶链表

给定单链表的头节点 head ,将所有索引为奇数的节点和索引为偶数的节点分别组合在一起,然后返回重新排序的列表。 O(1) 的额外空间复杂度和 O(n) 的时间复杂度

两个虚拟头结点,使用尾插法,然后合并到一起。

ListNode *odd = new ListNode(0);
ListNode *even = new ListNode(0);

 ListNode *tail1=odd;
 ListNode *tail2=even;
 ListNode *p = head;
 int idx=1;
  while(p!=nullptr){
       if(idx%2!=0){
                tail1->next=p;
                tail1=p;
                p=p->next;
                idx++;
        }else{
                tail2->next=p;
                tail2=p;
                p=p->next;
                idx++;
            }
        }
//最后需要把tail2->next置空
        tail2->next=nullptr;
        tail1->next=even->next;
        return odd->next;
 }

尾插法最后置空,否则会出现野指针错误。

LeetCode 25 k个一组翻转链表

使用栈,进栈k次,尾插法就是逆序的。

需要考虑剩下的链表个数够不够 k 个(因为不够 k 个不用翻转)。已经翻转的部分要与剩下链表连接起来。

stack<ListNode*>st
ListNode dummy(0)
ListNode* tail = &dummy
while (true):
      int count = 0;
      ListNode* p = head;
      / 将k个节点压入栈中
      while (p&&count<k):
           st.push(p);
           p=p->next;
           count++;
      if(count != k)
           tail->next=head
           break
      while (!stack.empty())
                tail->next = stack.top()
                stack.pop()
                tail = tail->next   
            tail->next = p
            head = p
return dummy->next
    

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/514947.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于SSM的网络视频播放器

目录 背景 技术简介 系统简介 界面预览 背景 互联网的迅猛发展彻底转变了全球各类组织的管理策略。自20世纪90年代起&#xff0c;中国政府和企业便开始探索利用网络系统进行信息管理。然而&#xff0c;早期的网络覆盖不广泛、用户接受度不高、相关法律法规不完善以及技术开…

备战蓝桥杯---DP刷题2

1.树形DP&#xff1a; 即问那几个点在树的直径上&#xff0c;类似ROAD那题&#xff0c;我们先求一下每一个子树根的子树的最大值与次大值用d1,d2表示&#xff0c;直径就是d1d2的最大值&#xff0c;那么我们如何判断是否在最大路径上&#xff0c;其实就是看一下从某一点出发的所…

YUNBEE云贝-技术分享:PostgreSQL分区表

引言 PostgreSQL作为一款高度可扩展的企业级关系型数据库管理系统&#xff0c;其内置的分区表功能在处理大规模数据场景中扮演着重要角色。本文将深入探讨PostgreSQL分区表的实现逻辑、详细实验过程&#xff0c;并辅以分区表相关的视图查询、分区表维护及优化案例&#xff0c;…

详解网络攻击的发生原因、类型及如何防范

网络攻击是访问计算机系统或者大小&#xff0c;修改或窃取数据的未经授权的企图。网络破坏分子可以使用多种攻击媒介&#xff0c;推出包括网络攻击的恶意软件&#xff0c;网络钓鱼&#xff0c;勒索&#xff0c;以及人在这方面的中间人攻击。固有风险和残余风险使这些攻击中的每…

LLM:检索增强生成(RAG)

1 Embedding技术 简单地说&#xff0c;嵌入(Embedding)思想可以视为一种尝试通过用向量来表示所有东西的“本质”的方法&#xff0c;其特性是“相近的事物”由相近的数表示。 1.1 文本向量(Text Embedding) 在GPT中&#xff0c;文本嵌入(Text Embedding)是通过将输入文本中的每…

Web Animations API 动画

Element.animate() dom.animate动画可以避免污染dom原有的css动画 参考资料 Element.animate() - Web API 接口参考 | MDN Element: getAnimations() method - Web APIs | MDN .tunnel{width:200px;height:200px;background-color:#38f;}<div class"tunnel" …

QT 实现无边框可伸缩变换有阴影的QDialog弹窗

实现无标题栏窗口的拖拽移动、调节窗口大小以及边框阴影效果。初始化时进行位或操作&#xff0c;将这些标志合并为一个值&#xff0c;并将其设置为窗口的标志。这些标志分别表示这是一个对话框、无边框窗口、有标题栏、有最小化按钮和最大化按钮。 setWindowFlags(Qt::Dialog |…

【微服务】——Nacos注册中心

这里写自定义目录标题 1.认识和安装Nacos2.服务注册到nacos1&#xff09;引入依赖2&#xff09;配置nacos地址3&#xff09;重启 3.服务分级存储模型3.1.给user-service配置集群3.2.同集群优先的负载均衡 4.权重配置5.环境隔离5.1.创建namespace5.2.给微服务配置namespace 6.Na…

蓝桥杯真题:货物摆放

import java.util.ArrayList;public class Main {public static void main(String args[]) {//常规思路/*long num 2021041820210418l;int count 0;for ( long i 1 ; i < num ; i ){for ( long j 1 ; j < num ; j ){for ( long k 1 ; k < num ; k ){if ( i * j *…

《C Prime Plus》02

1. UNIX 系统 C语言因UNIX系统而生&#xff0c;也因此而流行&#xff0c;所以我们从UNIX系统开始&#xff08;注意&#xff1a;我们提到的UNIX还包含其他系统&#xff0c;如FreeBSD&#xff0c;它是UNIX的一个分支&#xff0c;但是由于法律原因不使用该名称&#xff09;。 UN…

蓝桥杯练习——拼出一个未来

选中 index.html 右键启动 Web Server 服务&#xff08;Open with Live Server&#xff09;&#xff0c;让项目运行起来。接着&#xff0c;打开环境右侧的【Web 服务】&#xff0c;就可以在浏览器中看到如下效果&#xff1a; 目标 完善 js/index.js 的 TODO 部分&#xff0c;实…

概率、似然、极大似然估计

概率、似然、极大似然估计 概率&#xff1a;特定情况下某事件发生的可能性&#xff08;参数已知&#xff0c;事件发生的可能性&#xff09;似然&#xff1a;根据已经确定的结果推测产生这个结果的可能的环境&#xff08;事件发生的可能性已知&#xff0c;参数未知&#xff0c;推…

生成式AI的情感实验——AI能否产生思想和情感?

机器人能感受到爱吗&#xff1f;这是一个很好的问题&#xff0c;也是困扰了科学家们很多年的科学未解之谜。虽然我们尚未准备好向智能机器赋予情感&#xff0c;但智能机器却已经可以借助生成式人工智能&#xff08;AI&#xff09;来帮助我们表达自己的情感。 自然情感表达 AI正…

个人医疗开支预测项目

注意&#xff1a;本文引用自专业人工智能社区Venus AI 更多AI知识请参考原站 &#xff08;[www.aideeplearning.cn]&#xff09; 项目背景 随着医疗成本的持续上涨&#xff0c;个人医疗开支成为一个重要议题。理解影响医疗费用的多种因素对于医疗保险公司、政府机构以及个人…

Rust---复合数据类型之字符串与切片(2)

目录 字符串操作删除 (Delete)连接 (Concatenate) 字符串转义 前情回顾: Rust—复合数据类型之字符串&#xff08;1&#xff09; 字符串操作 删除 (Delete) 删除方法仅适用于 String 类型&#xff0c;分别是&#xff1a; pop()&#xff0c;remove()&#xff0c;truncate()&a…

【嵌入式DIY实例】-使用SCT-013 传感器测量交流电流

使用SCT-013 传感器测量交流电流 文章目录 使用SCT-013 传感器测量交流电流1、SCT-013介绍2、硬件准备2、如何计算电气设备消耗的电流3、代码实现SCT-013电流互感器在家用电能表中很常见。 它是一种无需断开电路即可测量导线中电流的组件。在本文中,我们将介绍如何使用 Arduin…

GraalVM运行模式和企业级应用

文章目录 GraalVM运行模式JIT模式AOT模式 GraalVM的问题和解决方案GraalVM企业级应用传统架构的问题Serverless架构函数计算Serverless应用场景Serverless应用 GraalVM内存参数 GraalVM运行模式 JIT模式 JIT&#xff08; Just-In-Time &#xff09;模式 &#xff0c;即时编译模…

绩效考核存在合理性、公平性、客观性吗?

目录 一、绩效考核流于形式&#xff1a;没有实际考核过 二、考核结果的确定: 主管一人说了算 三、考核结果&#xff1a; 与绩效奖金挂钩吗&#xff1f; 四、考核的滥用&#xff1a;成为公司排挤迫使员工离职的手段 五、公司说&#xff1a; 让你滚蛋&#xff0c;谁还会发你奖…

4.3学习总结

[HNCTF 2022 WEEK2]Canyource&#xff08;无参数&#xff09; 通过这题又接触了一种无参数RCE的方法&#xff0c;前面学习的getallheaders只有在apache环境下才能使用&#xff0c;具有一定的局限性 这里是利用php函数来构造读取flag的方法 localeconv() – 函数返回一个包含本…

满足小体积/低功耗/低成本需求,世强硬创推出CGM解决方案

随着CGM的普及与更多具备性价比的国产产品上市&#xff0c;越来越多的企业开始布局CGM市场。 为此全球领先的硬件创新研发和供应服务平台世强硬创面向硬科技企业推出CGM&#xff08;连续血糖监测&#xff09;解决方案。 该方案可一站式解决企业开发需求&#xff0c;包括系统整…