数据结构(单链表算法题)

  • 1.删除链表中等于给定值 val 的所有节点。 OJ链接

typedef struct ListNode ListNode;struct ListNode {int val;struct ListNode* next;
};struct ListNode* removeElements(struct ListNode* head, int val) {//创建新链表ListNode* newhead, *newtail;newhead = newtail = NULL;//遍历原链表ListNode* pcur = head;while (pcur){if (pcur->val != val)                            //遍历原链表,直到遍历至原链表的值与 val 的结点{if (newhead == NULL)                         //链表为空{newhead = newtail = NULL;}else                                         //链表不为空,将原链表的结点尾插到新链表中{newtail->next = pcur;newtail = newtail->next;}}pcur = pcur->next;}if (newtail)                                         //如果操作完后新的链表不为空,才能 newtail->next = NULL        ;           {newtail->next = NULL;}return newhead;}
  • 思路:创建新链表,将原链表中值不为val的结点尾插到新链表

  • 2.反转一个单链表。 OJ链接

struct ListNode* reverseList(struct ListNode* head) {//处理空链表if (head == NULL){return NULL;}//创建三个指针ListNode* n1, * n2, * n3;n1 = NULL; n2 = head;n3 = n2->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3){n3 = n3->next;}}return n1;
}
  • 思路:创建三个指针,在原链表上就可以修改指针的指向

原链表:       

循环一次后:

以此类推,当 n2 为 NULL 时跳出循环,此时 n1 指向的结点就是链表的新的头结点

(注意:在判断 n3 时要注意他是否已经跳出链表了,因为 n3 是移动的最快的,如果已经跳出链表就不能进行 ->next 操作) 

  • 3.给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。OJ链接

 

struct ListNode* middleNode(struct ListNode* head) {ListNode* slow=head, * fast=head;                 //创建两个指针,快慢指针while (fast && fast->next) {slow = slow->next;                            //慢指针每次走一步,快指针每次走两步fast = fast->next->next;}return slow;                                      //此时慢指针 slow 指向的节点刚好就是中间的结点
}
  • 思路:快慢指针,慢指针每次走一步,快指针每次走两步

当链表长度为奇数时:

 当链表长度为偶数时:

(注意:while 中的(fast && fast->next)顺序不能更改,当 fast 已经为空时,如果改成 

(fast->next && fast),条件会先按顺序执行 fast->next ,从而报错) 

  • 慢指针每次走一步,快指针每次走两步,当快指针走到链表的结尾时,假设链表的长度为 n ,快指针走的路程是慢指针的两倍,此时慢指针走的路程就是 n/2.

  •  4.输入一个链表,输出该链表中倒数第k个结点。 OJ链接

int kthToLast(struct ListNode* head, int k) {ListNode* fast = head,*slow=head;while (k--){fast = fast->next;}while (fast){slow = slow->next;fast = fast->next;}return slow->val;}
  • 思路:创建两个指针,1、先让 fast 向前走K步;
  •                                     2、slow 和 fast 同步前进,fast 到结尾,slow 到目标。

当 fast =NULL

  •  5.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。OJ链接

 

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {//处理链表为空if (list1 == NULL)                           //l1为空时,返回l2{return list2;}if (list2 == NULL)                           //l2为空时,返回l1{return list1;}ListNode* newhead, * newtail;               //创建新的链表newhead = newtail = (ListNode*)malloc(sizeof(ListNode));            //创建一个非空链表,减少了判断链表为空和非空情况导致的代码冗余ListNode* l1 = list1;                       //创建两个指针分别指向两个链表的头结点ListNode* l2 = list2;//进行比较尾插while (l1 && l2){if (l1->val < l2->val){newtail->next = l1;newtail = newtail->next;l1 = l1->next;}else{newtail->next = l2;newtail = newtail->next;l2 = l2->next;}}if (l1)                                     //跳出循环只用两种情况:要么 l1 为空(l2 肯定不为空);要么 l2 为空(l1 肯定不为空){newtail->next = l1;}if (l2){newtail->next = l2;}ListNode* ret = newhead->next;free(newhead);newhead = NULL;return ret;
}
  •  思路:创建新链表,遍历原链表,谁小就尾插到新链表中

  • 6.编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前 。OJ链接

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code hereListNode* lesshead,*lesstail;lesshead=lesstail=(ListNode*)malloc(sizeof(ListNode));   //大链表ListNode* greathead,*greattail;greathead=greattail=(ListNode*)malloc(sizeof(ListNode)); //小链表ListNode* pcur =pHead;                                //遍历链表while(pcur){if(pcur->val<x)                          //当原链表结点的值小于 x,尾插到小链表 {lesstail->next=pcur;lesstail=lesstail->next;}else                                    //当原链表结点的值大于 x,尾插到大链表 {greattail->next=pcur;greattail=greattail->next;}pcur=pcur->next;}greattail->next=NULL;                       //将大链表的尾结点的 next 指针置为NULLlesstail->next=greathead->next;              // 大小链表首尾相连ListNode* ret= lesshead->next;free(lesshead);free(greathead);lesshead=greathead=NULL;return ret;}
};
  •  思路:创建大链表、小链表,将小于 x 值的结点尾插到对应的链表中,最后小链表的尾与大链表的头相连。
  • (注意:不能忘了最后将大链表的 next 指针指向= NULL)

  • 7.链表的回文结构。OJ链接 

bool chkPalindrome(ListNode* A) {// write code hereListNode* mid=middleNode(A);           //找出原链表的中间结点ListNode*right=reverseList(mid);      //以次中间结点为头结点反转后面的链表ListNode*left=A;                    //从原链表和反链表比较结点的值while(right){if(left->val!=right->val){return false;}left=left->next;right=right->next;}return true;}
  • 思路:1、找出链表的中间结点
  •            2、将中间结点之后的链表进行反转
  •            3、从原链表和反链表比较结点的值

未完待续~~

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

解决TypeError: __init__() takes 1 positional argument but 2 were given

问题描述&#xff1a; 如下图&#xff0c;在使用torch.nn.Sigmoid非线性激活时报错 源代码&#xff1a; class testrelu(nn.Module):def __init__(self):super().__init__()self.sigmoid Sigmoid()def forward(self, input):output self.sigmoid(input)return outputwriter…

源码分析SpringCloud Gateway如何加载断言(predicates)与过滤器(filters)

我们今天的主角是Gateway网关&#xff0c;一听名字就知道它基本的任务就是去分发路由。根据不同的指定名称去请求各个服务&#xff0c;下面是Gateway官方的解释&#xff1a; Spring Cloud Gateway&#xff0c;其他的博主就不多说了&#xff0c;大家多去官网看看&#xff0c;只…

vue和微信小程序的区别、比较

找到一篇很好的关于vue和小程序之间的理解文章&#xff0c;在此分享一下&#xff1a; 前端 - vue和微信小程序的区别、比较 - 个人文章 - SegmentFault 思否https://segmentfault.com/a/1190000015684864

huawei USG6001v1学习---信息安全概念

目录 1.什么是分布式&#xff1f; 2.什么是云计算&#xff1f; 3.APT攻击 4.安全风险能见度不足 5.常见的一些攻击 6.交换机转发原理&#xff1f; 7.各层攻击类型 7.1链路层&#xff1a; 7.2网络层&#xff1a; 7.3传输层&#xff1a; 7.4应用层&#xff1a; 1.什么…

github上的工程如何下载子模块.gitmodules如何下载指定的模块download submodules开源项目子模块下载externals

github上的工程如何下载子模块.gitmodules如何下载指定的模块download submodules 说明(废话)解决方案无法执行下载子模块无法下载子项目 说明(废话) 今天在编译一个开源库时&#xff0c;该开源库依赖其他项目&#xff0c;并且项目还挺多的&#xff0c;所以有此解决方案 在编…

云微客如何实现低成本快速获客?AI矩阵来传播

目前市场环境较为严峻&#xff0c;超过上千万家实体商家都会遇到线下获客难、线上营销成本高的困境&#xff0c;因此商家急需新的获客方案。 云微客AI矩阵系统基于AIGC的企业短视频矩阵及内容生成、协作、管理平台&#xff0c;通过对多个短视频平台进行营销覆盖&#xff0c;深入…

新建一个git仓库并且把已有项目推送到git远程仓库

总贴 1. 创建一个空项目&#xff0c;不会看新建仓库 2. 克隆这个项目到某个文件夹去&#xff0c;比如我想克隆到我的E盘的code下面 3. 我的这个文件夹下面是有东西的&#xff0c;一点都不影响 . 4. 用命令行进入这个文件夹 命令行已经显示了已经在E盘下面code文件夹, 不会…

el-tree动态添加子节点的问题

如果我们需要动态往el-tree里面某一个节点添加子节点&#xff0c;追加或删除&#xff0c;我跟你讲&#xff0c;一定要显式地调用el-tree的方法&#xff0c;不然的话&#xff0c;后面调用setChecked这种方法看不到效果的。 比如el-tree绑定的data如下&#xff1a; [{id:"1…

Elasticsearch:如何选择向量数据库?

作者&#xff1a;来自 Elastic Elastic Platform Team 向量数据库领域是一个快速发展的领域&#xff0c;它正在改变我们管理和搜索数据的方式。与传统数据库不同&#xff0c;向量数据库以向量的形式存储和管理数据。这种独特的方法可以实现更精确、更相关的搜索&#xff0c;并允…

逆向案例二十五——webpack所需模块函数很多,某翼云登录参数逆向。

解决步骤&#xff1a; 网址&#xff1a;aHR0cHM6Ly9tLmN0eXVuLmNuL3dhcC9tYWluL2F1dGgvbG9naW4 不说废话&#xff0c;密码有加密&#xff0c;直接搜索找到疑似加密位置打上断点。 再控制台打印&#xff0c;分析加密函数 有三个处理过程&#xff0c;b[g]得到的是用户名,b[f] 对…

React@16.x(62)Redux@4.x(11)- 中间件2 - redux-thunk

目录 1&#xff0c;介绍举例 2&#xff0c;原理和实现实现 3&#xff0c;注意点 1&#xff0c;介绍 一般情况下&#xff0c;action 是一个平面对象&#xff0c;并会通过纯函数来创建。 export const createAddUserAction (user) > ({type: ADD_USER,payload: user, });这…

如何在Mac下修改VSCode侧边栏字体大小

在日常使用VSCode&#xff08;Visual Studio Code&#xff09;进行开发时&#xff0c;我们有时需要对IDE&#xff08;集成开发环境&#xff09;的界面进行一些个性化的调整&#xff0c;以提升我们的开发体验。 比如&#xff0c;有些用户可能会觉得VSCode的侧边栏字体大小不符…

uni-app开发日志:unicloud使用时遇到的问题解决汇总(不断补充)

插件安装后提示与原数据库表冲突&#xff08;2024.7.18&#xff09; 安装uni-admin后再安装uni-cms&#xff0c;在uni-admin中添加好菜单&#xff0c;结果提示该错误 回到hbuilder中uniCloud/database中找到冲突的部分 比较一下&#xff0c;选中老的删除 opendb-news-articl…

PCB(印制电路板)制造涉及的常规设备

印制电路板&#xff08;PCB&#xff09;的制造涉及多种设备和工艺。从设计、制作原型到批量生产&#xff0c;每个阶段都需要不同的专业设备。以下是一些在PCB制造过程中常见的设备&#xff1a; 1. 计算机辅助设计&#xff08;CAD&#xff09;软件&#xff1a; - 用于设计PC…

Linux——Shell脚本和Nginx反向代理服务器

1. Linux中的shell脚本【了解】 1.1 什么是shell Shell是一个用C语言编写的程序&#xff0c;它是用户使用Linux的桥梁 Shell 既是一种命令语言&#xff0c;有是一种程序设计语言 Shell是指一种应用程序&#xff0c;这个应用程序提供了一个界面&#xff0c;用户通过这个界面访问…

WPF/C#:实现导航功能

前言 在WPF中使用导航功能可以使用Frame控件&#xff0c;这是比较基础的一种方法。前几天分享了wpfui中NavigationView的基本用法&#xff0c;但是如果真正在项目中使用起来&#xff0c;基础的用法是无法满足的。今天通过wpfui中的mvvm例子来说明在wpfui中如何通过依赖注入与M…

Axure中继器进阶指南:打造专业级交互

中继器进阶篇 前言 经过了基础篇的学习,我们已经掌握了中继器的基本操作,接下来来解锁中继器的进阶操作。 1. 修改删除指定行 首先拖入中继器,加上【修改】 【删除】的按钮,然后给修改按钮添加单击事件选择【更新行】。 这里可以看到我们在中继器内部添加的事件,在编…

Linux编辑器——vim的使用

目录 vim的基本概念 命令模式 底行模式 插入模式 注释和取消注释 普通用户进行sudo提权 vim配置问题 vim的基本概念 一般使用的vim有三种模式&#xff1a; 命令模式 底行模式和插入模式&#xff0c;可以进行转换&#xff1b; vim filename 打开vim&#xff0c;进入的…

ElmoCha——体验最好的 web 内容 AI 总结插件

介绍 最近我用了很多网页总结产品&#xff0c;share 一下我认为最好用的 web 总结的 AI 插件。 当前体验最好的 web 内容总结插件&#xff1a;ElmoChat&#xff0c;由 Lepton 开发&#xff0c;可以生成网页总结、摘要、观点、相关问题。 非常方便的是&#xff0c;总结的内容提…

HarmonyOS根据官网写案列~ArkTs从简单地页面开始

Entry Component struct Index {State message: string 快速入门;build() {Column() {Text(this.message).fontSize(24).fontWeight(700).width(100%).textAlign(TextAlign.Start).padding({ left: 16 }).fontFamily(HarmonyHeiTi-Bold).lineHeight(33)Scroll() {Column() {Ba…