链表OJ练习一(精选OJ题)

news/2024/11/24 21:02:48/

前言

我们在前面学习了单链表的基本知识，我们需要运用它，才可以掌握它，所以我们选了几个经典OJ题，大家可以做做看着自己掌握没有 。

这时练习一，就有练习二,大家可以直接点击过去。

OJ练习

(1)删除链表中等于给定值 val 的所有结点。

在这里插入图片描述

思路：我们可以先遍历一遍链表，在遍历的过程中，我们可以将其中不等于val的值尾插到一个新链表中，然后将等于val的结点直接删除。

struct ListNode* removeElements(struct ListNode* head, int val){//用新指针代表链表的移动struct ListNode* cur =head;//创建一个新链表，来进行尾插struct ListNode* newhead ,*tail;newhead = tail =NULL;//将上面这个链表遍历一遍while(cur){//判断跟val是否相等if(cur->val!=val){//如果第一个是空指针，就直接赋给它，第一个不是空指针就尾插if(tail==NULL){newhead = tail = cur;cur = cur->next;}else{tail ->next = cur;tail = tail->next;cur=cur->next;}} //如果不等于val就直接跳过else if(cur->val==val){cur=cur->next;}}//防止最后一个结点等于valif(tail->next != NULL)tail->next = NULL;return newhead; 
}

在这里插入图片描述

我们发现程序并不能跑过去，我想进行调试但是好像不能进行调试，所以我们为了调试可以用自己写过的链表稍加修改就可以进行调试了，
这个工作确实有点难度，但是是提升自己能力的时候，我们不能放弃。

自己构建链表进行调试

下面是我的链表调试代码，大家可以参考一下。

#define _CRT_SECURE_NO_WARNINGS 1 
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//动态开辟链表
SLTNode* BuySLTNode(SLTDataType n)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->data = n;newnode->next = NULL;return newnode;
}
//创建n个链表
SLTNode* CreatSList(int* arr)
{SLTNode* phead = NULL;SLTNode* ptail = NULL;for (int i = 0; i < 5; i++){SLTNode* newnode = BuySLTNode(arr[i]);if (phead == NULL){phead = ptail = newnode;}else{ptail->next = newnode;ptail = newnode;}}return phead;
}//单链表的释放
void SLTDestroy(SLTNode** pphead)
{SLTNode* cur = *pphead;while (cur){SLTNode* next = cur->next;free(cur);cur = next;}
}void SLTPushFront(SLTNode** pphead, SLTNode* cur)
{cur->next = *pphead;*pphead = cur;
}int main()
{int arr[7] = { 1,2,6，3，4，5，6};SLTNode* plist = CreatSList(arr);}

有了这个我们将上面的题目复制粘贴到我们的代码上我们就可以自己进行调试了。

我们发现两个问题，
第一个问题：如果链表是空链表的时候，我们没有处理。
第二个问题：在遍历完一遍链表，newhead还是空链表的时候，我们最后一步if判断进行了空链表的引用。
我们这时侯就感谢我们的自己构建的链表，在进行调试的时候，就可以解决了。

最后代码

truct ListNode* removeElements(struct ListNode* head, int val){//用新指针代表链表的移动struct ListNode* cur =head;//创建一个新链表，来进行尾插struct ListNode* newhead ,*tail;newhead=tail=NULL;//防止是空链表if(head==NULL){return NULL;}//将上面这个链表遍历一遍while(cur){//判断跟val是否相等if(cur->val!=val){//如果第一个是空指针，就直接赋给它，第一个不是空指针就尾插if(tail==NULL){newhead = tail = cur;cur = cur->next;}else{tail ->next = cur;tail = tail->next;cur=cur->next;}} //如果不等于val就直接跳过else if(cur->val==val){cur=cur->next;}}//防止最后一个结点等于valif(tail != NULL)tail->next = NULL;return newhead; 
}

拓展(使用哨兵位的头结点来做这个题)

为什们用哨兵位的头结点呢？
我们在尾删或者尾插的时候，可能我们在插或删的过程中，会遇到空链表，在插入的时候，需要用二级指针。但是我们用哨兵位的头结点的时候，我们就不需要考虑这个问题，因为无论如何我们都有一个哨兵位，不会成为空链表，所以我们用起来更舒服。

用哨兵位的头结点，很好尾插，所以我们遇到尾插的时候就可以用哨兵位的头结点。

struct ListNode* removeElements(struct ListNode* head, int val){//用新指针代表链表的移动struct ListNode* cur =head;//创建一个新链表，来进行尾插struct ListNode* guard,*tail;//创建一个表头guard = tail=(struct ListNode*)malloc(sizeof(struct ListNode));guard->next=NULL;//防止是空链表if(head==NULL){return NULL;}//将上面这个链表遍历一遍while(cur){//判断跟val是否相等if(cur->val!=val){//现在就直接尾插就可以了，不用分两种情况tail->next=cur;cur=cur->next;tail=tail->next;} //如果不等于val就直接跳过else if(cur->val==val){cur=cur->next;}}tail->next = NULL;return guard->next; 
}

(2)反转链表

在这里插入图片描述

思路一：创建一个新链表，然后进行头插
思路二：将链表的箭头直接反过来不久好了吗

思路一：头插

struct ListNode* reverseList(struct ListNode* head){struct ListNode* newhead ;struct ListNode* cur, *next;cur  = head;newhead = NULL;while (cur){next=cur->next;cur->next=newhead;newhead=cur;cur=next;}return newhead;
}

思路二：将箭头直接改变方向

在这里插入图片描述

我们想要实现这个东西，我们就要用三个指针，来进行链表方向的改动
n1和n2来进行方向的改变，而n3进行保留下一个结点的地址。

struct ListNode* reverseList(struct ListNode* head){//我们看着图命名struct ListNode* n1=NULL;struct ListNode* n2=head;struct ListNode* n3;//防止链表是空指针if(head!=NULL)n3=head->next;//循环的条件是就是n2等于空指针的时候while(n2){n2->next=n1;n1=n2;n2=n3;//防止n3是空指针，形成空指针的解引用if(n3!=NULL)n3=n3->next;}return n1;}

(3)合并两个有序链表

在这里插入图片描述

思路:创建一个新的链表，然后一个一个比较，然后在尾插，直到我们尾插完，我们上面说了尾插的时候，我们用哨兵位的头结点，这样简单

代码如下

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){//创建一个哨兵位的新链表struct ListNode* Newhead,*tail;Newhead=tail=(struct ListNode*)malloc(sizeof(struct ListNode));Newhead->next=NULL;struct ListNode* cur1=list1;struct ListNode* cur2=list2;//空链表直接返回空指针if(list1==NULL&&list2==NULL){return NULL;}//将两个链表进行遍历//循环的条件就是其中一个链表走完就是结束了while(cur1&&cur2){//将list1的链表尾插if(cur1->val<=cur2->val){tail->next=cur1;cur1=cur1->next;tail=tail->next;}//将list2的链表尾插else{tail->next=cur2;cur2=cur2->next;tail=tail->next;}}//将其中剩下的一个链表尾插上去if(cur1==NULL){tail->next=cur2;}else if(cur2 ==NULL){tail->next=cur1;}//提交的是哨兵位头结点的下一个return Newhead->next;
}

(4)链表的中间结点

在这里插入图片描述

思路：其实这道题考验的是逻辑问题，中间结点有两种
一个是奇数的中间结点，奇数的中间结点是就是中间的那一个
另一个是偶数的中间结点，偶数的中间结点有两个，我们选后面的那个

这时，我们想一下，我们在找的都是中间的东西，那么现在有一只猫和一只狗，已知狗的速度是猫的二倍，那么问题是等狗到终点，我们的猫在哪里。
很显然猫在离终点的一半位置。

所以我们可以按照这个思路，我能整两个指针，然后一个指针正常走，另一个指针的速度是他的二倍。我们找到中点就是我们的第一个指针。
在这里插入图片描述

从图中我们可以看出，
当是奇数的时候，当fast的next等于NULL的时候停下来。
当是偶数的时候，当fast等于NULL的时候停下来
代码如下

struct ListNode* middleNode(struct ListNode* head){struct ListNode* slow =head;struct ListNode* fast=head;//条件就是当fast的next或fast等于NULLwhile(fast&&fast->next){slow=slow->next;fast=fast->next->next;}return slow;
}

(5)链表中倒数第k个结点

其实跟上一题的思路基本一致，也是速度差
但是我们找倒数第几个，先有两个指针，然后我们先将第一步将两个指针的距离隔上k步然后再依次走，直到fast等于空指针停下来。

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* slow = pListHead;struct ListNode* fast = pListHead;struct ListNode* num = pListHead;int i=0;while(num){num=num->next;i++;}if(k>i){return NULL;}while(k--){fast=fast->next;}while(fast){slow=slow->next;fast=fast->next;}return slow;
}

(6)链表分割

在这里插入图片描述

其实思路还是很好写的，关键是代码的编写，
思路是先将比X小的创建一个链表，然后将比X大的创建一个链表，然后将链表合并。

代码如下

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {//用哨兵位的链表struct ListNode* SmallList,*GreatList,*Stail,*Gtail;GreatList=Gtail=(struct ListNode*)malloc(sizeof(struct ListNode));SmallList=Stail=(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur = pHead;Gtail->next=NULL;Stail->next=NULL;//将小于x的值放到小的链表上去while(cur){if(cur->val<x){Stail->next=cur;Stail=Stail->next;}else if(cur->val>=x){Gtail->next=cur;Gtail=Gtail->next;}cur=cur->next;     }//将链表合并Stail->next=GreatList->next;Gtail->next=NULL;pHead=SmallList->next;free(SmallList);free(GreatList);return pHead;}
};

(7)链表的回文结构

在这里插入图片描述

思路：我们先运用速度差，将来改链表分为两个链表，然后再将第二个链表反转，最后再将两个链表比较，直到第一个链表为空，如果相等，那么就是回文链表，不然则不是。

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/struct ListNode* reverseList(struct ListNode* head){//我们看着图命名struct ListNode* n1=NULL;struct ListNode* n2=head;struct ListNode* n3;//防止链表是空指针if(head!=NULL)n3=head->next;//循环的条件是就是n2等于空指针的时候while(n2){n2->next=n1;n1=n2;n2=n3;//防止n3是空指针，形成空指针的解引用if(n3!=NULL)n3=n3->next;}return n1;}class PalindromeList {
public:bool chkPalindrome(ListNode* A) {struct ListNode* slow =A;struct ListNode* fast=A;struct ListNode* pre =A;//条件就是当fast的next或fast等于NULLwhile(fast&&fast->next){pre=slow;slow=slow->next;fast=fast->next->next;}//将链表一分为二pre->next=NULL;//反转链表slow=reverseList(slow);//判断是否是回文链表while(A){if(A->val==slow->val){A=A->next;slow=slow->next;}else{return false;}}return true;}
};

总结

这个就是对于单链表知识理解没有的掌握，我们将这些题做完，我们就会对我们的链表知识的掌握更加深刻。


http://www.ppmy.cn/news/22846.html

相关文章

数据结构与算法-单链表

数据结构与算法-单链表

Java高级系列文章前言 本文章涉及到数据结构与算法的知识&#xff0c;该知识属于Java高级阶段&#xff0c;通常为学习的二阶段&#xff0c;本系列文章涉及到的内容如下&#xff08;橙色框选内容&#xff09;&#xff1a; 本文章核心是教学视频&#xff0c;所以属于个人笔记&a…
阅读更多...
【Java多线程】创建多线程方式三：实现Callable接口

【Java多线程】创建多线程方式三：实现Callable接口

实现Callable接口是JDK5.0新增线程创建方式 与使用Runnable相比&#xff0c; Callable功能更强大些 1.相比run()方法&#xff0c;可以有返回值 2.方法可以抛出异常 3. 支持泛型的返回值 4.需要借助FutureTask类&#xff0c;比如获取返回结果 Future接口 1. 可以对具体Ru…
阅读更多...
Android基础教程——从入门到精通（下）

Android基础教程——从入门到精通（下）

本文是对B站教程 动脑学院 Android教程 学习过程中所做的笔记。文章分为上下两部分&#xff0c;此文是下部分&#xff0c;上部分链接为&#xff1a;Android基础教程——从入门到精通&#xff08;上&#xff09;。源视频教程并没有录制全&#xff0c;本文还补充了 Service 和 网…
阅读更多...
google超强插件助力提升网站可访问性，排名直线提升

google超强插件助力提升网站可访问性，排名直线提升

前情摘要 对于我们几乎所有人来说&#xff0c;网络是日常生活中不可或缺的一部分。全世界&#xff0c;五分之一的人有残疾——视觉、听觉、运动或认知——这可能使他们难以或无法使用网站。过去&#xff0c;残疾人无法使用其网站的组织可以简单地提供替代方案&#xff0c;例如…
阅读更多...
SpringBoot项目启动报错踩坑

SpringBoot项目启动报错踩坑

目录一、redis和jedis版本不匹配二、spring循环依赖2.1、方法12.2、方法2三、允许DefaultServlet默认注册3.1、方法13.2、方法2四、debug运行报错4.1、方法14.2、方法2一、redis和jedis版本不匹配 报错日志如下&#xff1a; Caused by: java.lang.ClassNotFoundException: re…
阅读更多...
【Quick-Cocos2dx-Commucity】Windows平台发布游戏

【Quick-Cocos2dx-Commucity】Windows平台发布游戏

文章目录前言操作步骤前言 本示例使用Quick-Cocos2dx-Commucity开发&#xff0c;用VS2019打包发布游戏。演示简易的打包Win平台下的游戏.exe。 操作步骤 1. 首先这是开发的文档&#xff1a; frameworks: 存放Cocos2d-x引擎核心代码及各个平台运行时资源res&#xff1a;存放…
阅读更多...
Obsidian 插件（二）：Advanced_Slides 的使用

Obsidian 插件（二）：Advanced_Slides 的使用

文章目录Advanced Slides 的使用一、 概述1、 简介2、 特征3、 第一个 PPT二、 基础语法1、 水平垂直幻灯片2、 元素注释3、 幻灯片注释4、 块注解5、 元素动画6、 内联样式7、 幻灯片背景样式8、 演讲者模式9、 列表动画10、 画图支持11、 图标12、 表情包13、 图表支持14、 幻…
阅读更多...
【Node.js实战】一文带你开发博客项目之初识Koa2（koa2安装使用、搭建开发环境、测试路由）

【Node.js实战】一文带你开发博客项目之初识Koa2（koa2安装使用、搭建开发环境、测试路由）

个人简介 &#x1f440;个人主页&#xff1a; 前端杂货铺 &#x1f64b;‍♂️学习方向&#xff1a; 主攻前端方向&#xff0c;也会涉及到服务端 &#x1f4c3;个人状态&#xff1a; 在校大学生一枚&#xff0c;已拿多个前端 offer&#xff08;秋招&#xff09; &#x1f680;未…
阅读更多...
最新文章

Copyright @ 2022~2023