链表--经典题

题目一:移除链表元素

示例 1:

输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]

示例 2:

输入:head = [], val = 1
输出:[]

示例 3:

输入:head = [7,7,7,7], val = 7
输出:[]

本题是要求我们在链表中移除给定的元素,当我们凭空很难打开思路时我们这时就可以通过画图来理清思路在来进行敲代码。

struct ListNode {
	int val;
	struct ListNode* next;
	
};
typedef struct ListNode ListNode;
ListNode* removeElements(ListNode* head, int val)
{
	ListNode* newhead = NULL;//定义新节点的头节点
	ListNode* newtail = NULL;//定义新节点的尾节点
	ListNode* pcur = head;
	while (pcur)//遍历整个链表
	{
		if (pcur->val != val)
		{
			if (pcur == NULL)
			{
				return head;//如果原链表为空的话直接返回
			}
			else
			{
				newtail->next = pcur;
				newtail = newtail->next;
			}
		}
		pcur = pcur->next;
	}
	if (newtail != NULL)
	{
		newtail->next = NULL;//将新链表尾节点指向空,不然会报错
	}
	return newhead;
}

 这个题主要是将指点节点删除我们有两种思路,我采用的是思路2,本题需要特别注意的是当新链表尾插完成之后要将尾节点进行制空,不然程序会报错。

 

题目二:反转链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

示例 2:

输入:head = [1,2]
输出:[2,1]

示例 3:

输入:head = []
输出:[]

本题我们还是先画图来进行分析在进行代码的实现。

 

//将链表进行反置
struct ListNode {
	int val;
	struct ListNode* next;
	
};

typedef struct ListNode ListNode;
ListNode* reverseList(ListNode* head)
{
	//首先定义三个指针
	ListNode* n1 = NULL;
	ListNode* n2 = head;
	ListNode* n3 = n2->next;
	//要先判断链表是否为空,如果为空的话直接返回
	if (head == NULL)
	{
		return head;
	}

	while (n2 != NULL)
	{
		n1 = n2->next;
		n1 = n2;
		n2 = n3;
		if(n3!=NULL)
			n3 = n3->next;//这里要考虑当n3=NULL指针时n3->next就是错误代码程序会报错
	}
	return n1;//最后n1就是反转后链表的头节点直接返回n1就是反转后的链表
}

 本题的解题思路我们可以通过画图进行求解,画图我们可以发现我们只需想办法将链表的指向进行反转,我们就可以通过这个思路进行敲代码进行实现。 

题目三:链表的中间节点

给你单链表的头结点 head ,请你找出并返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点。

示例 1:

输入:head = [1,2,3,4,5]
输出:[3,4,5]
解释:链表只有一个中间结点,值为 3 。

示例 2:

输入:head = [1,2,3,4,5,6]
输出:[4,5,6]
解释:该链表有两个中间结点,值分别为 3 和 4 ,返回第二个结点。

本题要我们求链表的中间节点有两种情况,就是链表为节点个数为奇数和偶数两种情况,那我们怎么解决这个题呢?还是按照先画图在进行代码实现的方法。

 

 

struct ListNode {
	int val;
	struct ListNode* next;
	
};
typedef struct ListNode ListNode;
ListNode* middleNode(ListNode* head)
{
	ListNode* show = head;
	ListNode* fast = head;
	while (fast&&fast->next)
	{
		show = show->next;
		fast = fast->next->next;
	}
	return show;
}

本题当我们画图想出了快慢指针的方法是我们就可以很轻松的解决这道题。 

 

题目四:合并两个有序链表

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

示例 1:

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例 2:

输入:l1 = [], l2 = []
输出:[]

示例 3:

输入:l1 = [], l2 = [0]
输出:[0]

 本题要求我们将两个链表进行升序合并,同样我们解决本题同样需要我们画图理清思路之后再来进行代码实现。

struct ListNode {
	int val;
	struct ListNode* next;
};
typedef struct ListNode* ListNode;
ListNode* mergeTwoLists(ListNode* list1,ListNode* list2) {
	//首先进行判空操作
	if (list1 == NULL)
	{
		return list2;
	}
	if (list2 == NULL)
	{
		return list1;
	}
	
	
	ListNode* l1 = list1;
	ListNode* l2 = list2;

	ListNode* newhead = NULL;
	ListNode* newtail = NULL;
	while (l1 && l2)
	{
		if(l1->val>l2->val)
		{ 
			//尾插l2
			if (newhead == NULL)
			{
				newhead = newtail = l2;
			}
			else
			{
				newtail->next = l2;
				newtail = newtail->next;
			}
			l2 = l2->next;
		}
		else
		{
			//尾插l1
			if (newhead == NULL)
			{
				newhead = newtail = l1;
			}
			else
			{
				newtail->next = l1;
				newtail = newtail->next;
			}
			l1 = l1->next;
		}
	}
	if (l2)
	{
		newtail->next = l2;
	}
	if (l1)
	{
		newtail->next = l1;
	}
	return newhead;
}

本题我们可以通过比较两个原链表将较小的那一个节点尾插到新链表中。

题目五:分割链表

给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。

示例 1:

输入:head = [1,4,3,2,5,2], x = 3
输出:[1,2,2,4,3,5]

示例 2:

输入:head = [2,1], x = 2
输出:[1,t

本题要求我们分割链表将大于x的节点放在后面将小于x的链表放在前面,我们先画图理清思路在进行代码实现。

 

struct ListNode {
	int val;
	struct ListNode* next;
};
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x) {
    if (head == NULL)
    {
        return head;
    }
    ListNode* lesshead, * lesstail;
    ListNode* greaterhead, * greatertail;
    //创建新的大小链表
    lesshead = lesstail = (ListNode*)malloc(sizeof(ListNode));
    greaterhead = greatertail = (ListNode*)malloc(sizeof(ListNode));
    ListNode* pcur = head;
    while (pcur)
    {
        if (pcur->val < x)
        {
            lesstail->next = pcur;
            lesstail = lesstail->next;
        }
        else
        {
            greatertail->next = pcur;
            greatertail = greatertail->next;
        }
        pcur = pcur->next;
    }
    lesstail->next = greaterhead->next;//将大小链表进行首尾相连
    greatertail->next = NULL;//如果不加这一行程序将会报错
    ListNode* ret = lesshead->next;
    free(lesshead);
    free(greaterhead);
    lesshead = greaterhead = NULL;
    return ret;
}

题目六:环形链表的约瑟夫问题

描述

编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数,报到 m 的人离开。

下一个人继续从 1 开始报数。

n-1 轮结束以后,只剩下一个人,问最后留下的这个人编号是多少?

数据范围: 1≤n,m≤100001≤n,m≤10000

进阶:空间复杂度 O(1),时间复杂度 O(n)

示例1

输入:

5,2     

返回值:

3    

说明:

开始5个人 1,2,3,4,5 ,从1开始报数,1->1,2->2编号为2的人离开
1,3,4,5,从3开始报数,3->1,4->2编号为4的人离开
1,3,5,从5开始报数,5->1,1->2编号为1的人离开
3,5,从3开始报数,3->1,5->2编号为5的人离开
最后留下人的编号是3      

示例2

输入:

1,1

返回值:

1

 

本题我们一样要先进行画图分析之后才能求解。

 

typedef struct ListNode ListNode;
 ListNode* buyNode(int x)
 {
    ListNode* node=(ListNode*)malloc(sizeof(ListNode));
    if(node==NULL)
    {
        exit(1);
    }
    node->val=x;
    node->next=NULL;
    return node;
 }
 ListNode* creatCircle(int n)
 {
    ListNode* phead=buyNode(1);
    ListNode* ptail=phead;
    for(int i=2;i<=n;i++)
    {
        ptail->next=buyNode(i);
        ptail=ptail->next;
    }
    ptail->next=phead;
    return ptail;
 }
int ysf(int n, int m ) {
    ListNode* prev=creatCircle(n);
    ListNode* pcur=prev->next;
    int count=1;
    while(pcur->next!=pcur)
    {
        if(count==m)
        {
            prev->next=pcur->next;
            free(pcur);
            pcur=prev->next;
            count=1;
        }
        else {
        {
            prev=pcur;
            pcur=pcur->next;
            count++;
        }
        }
    }
    return pcur->val;
}

总结:

这六个题都是关于链表的题型当我们再做这种题型的时候我觉得更多的是需要我们图形结合的思想,画图能让我们尽快的打开思路,再通过画图的思路去进行代码实现这时就会容易很多!

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

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

相关文章

【转】关于vsCode创建后,不显示NPM脚本解决

刚刚使用vue ui新建了个vue项目&#xff0c;打开vs-code发现&#xff0c;无论怎么设置都找不到NPM脚本显示&#xff0c;苦恼了很久&#xff0c;突然发现&#xff01;打开了package-lock.json&#xff0c;然后立马把vs-code关闭&#xff0c;重新打开&#xff0c;就显示了npm脚本…

计算机网络(三)数据链路层

数据链路层 基本概念 数据链路层功能&#xff1a; 在物理层提供服务的基础上向网络层提供服务&#xff0c;主要作用是加强物理层传输原始比特流的功能&#xff0c;将物理层提供的可能出错的物理连接改在为逻辑上无差错的数据链路&#xff0c;使之对网络层表现为一条无差错的…

03-echarts如何画立体柱状图

echarts如何画立体柱状图 一、创建盒子1、创建盒子2、初始化盒子&#xff08;先绘制一个基本的二维柱状图的样式&#xff09;1、创建一个初始化图表的方法2、在mounted中调用这个方法3、在方法中写options和绘制图形 二、画图前知识1、坐标2、柱状图图解分析 三、构建方法1、创…

构建高效协同平台架构:实现团队协作的新高度

随着企业规模的扩大和工作方式的变革&#xff0c;团队协作变得愈发重要。在这个数字化时代&#xff0c;构建一个高效的协同平台架构&#xff0c;能够为团队提供强大的工具和资源&#xff0c;实现更加高效、灵活的协作方式。本文将探讨协同平台架构的重要性&#xff0c;并介绍如…

UE5不打包启用像素流 ubuntu22.04

首先查找引擎中像素流的位置&#xff1a; zkzk-ubuntu2023:/media/zk/Data/Linux_Unreal_Engine_5.3.2$ sudo find ./ -name get_ps_servers.sh [sudo] zk 的密码&#xff1a; ./Engine/Plugins/Media/PixelStreaming/Resources/WebServers/get_ps_servers.sh然后在指定路径中…

笔试的解题思路很多,

昨天发的笔试题目&#xff0c;留言的人还挺多&#xff0c;这道笔试题目是字节的嵌入式笔试题目&#xff0c;从面试的朋友描述说&#xff0c;对方的面试过程很专业。 现场写代码&#xff0c; 金三银四一直是铁律&#xff0c;去年我一个朋友离职后&#xff0c;也是最近这几天拿到…

【C语言】预处理

个人主页点这里~ 预处理 一、预处理符号二、#define定义常量三、#define定义宏四、带有副作用的宏参数五、宏替换的规则六、宏与函数的对比&#xff08;一&#xff09;、宏的优势&#xff08;二&#xff09;、宏的劣势&#xff08;三&#xff09;、宏和函数的对比 七、#和##1、…

Emacs之增加/取消输入括号自动匹配(一百三十六)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…

vue webpack打包配置生成的源映射文件不包含源代码内容、加密混淆压缩

前言&#xff1a;此案例使用的是vue-cli5 一、webpack源码泄露造成的安全问题 我们在打包后部署到服务器上时&#xff0c;能直接在webpack文件下看到我们项目源码&#xff0c;代码检测出来是不安全的。如下两种配置解决方案&#xff1a; 1、直接在项目的vue.config.js文件中加…

C语言 | Leetcode C语言题解之第30题串联所有单词的子串

题目&#xff1a; 题解&#xff1a; typedef struct {char key[32];int val;UT_hash_handle hh; } HashItem;int* findSubstring(char * s, char ** words, int wordsSize, int* returnSize){ int m wordsSize, n strlen(words[0]), ls strlen(s);int *res (int *)mall…

【测试开发学习历程】python常用的模块(中)

目录 5 time模块 5.1、Python中的四种格式的时间&#xff1a; 5.2、time模块中的常用函数 6 I/O流操作 6.1 创建文件 6.2 读取一个文件存入到另外一个文件 6.3 with open as 结构 6.4 open和with open as的区别 7 Excel的操作模块-openpyxl 7.1、新建Excel文件进行读…

11.范式与反范式设计

范式 1.问题 MySQL的库表设计&#xff0c;在很多时候我们都是率性而为&#xff0c;往往在前期的设计中考虑不全面&#xff0c;同时对于库表结构的划分也并不明确&#xff0c;所以很多时候在开发过程中&#xff0c;代码敲着敲着会去重构某张表结构&#xff0c;甚至大面积重构多…

bestvike 资料 --Spring Boot 2.5.0

Spring Boot 2.5.0 SSM环境搭建 springspringmvcmybatisspring springmvc mybatis # 项目 - 需求分析 概要设计(库表设计) 详细设计(验证库表正确性) 编码(环境搭建业务代码) 测试 部署上线# 员工添加 查询所有功能 SSM - 库表 库: ssm 数据库:mysql 表: id na…

spring-cloud微服务gateway

核心部分&#xff1a;routes(路由)&#xff0c; predicates(断言)&#xff0c;filters(过滤器) id&#xff1a;可以理解为是这组配置的一个id值&#xff0c;请保证他的唯一的&#xff0c;可以设置为和服务名一致 uri&#xff1a;可以理解为是通过条件匹配之后需要路由到&…

RabbbitMQ基本使用及其五种工作模型

初识MQ 同步通讯和异步通讯 什么是同步通讯呢&#xff1f;举个例子&#xff0c;你认识了一个小姐姐&#xff0c;聊的很火热&#xff0c;于是你们慢慢开始打电话&#xff0c;视频聊天&#xff0c;这种方式就成为同步通讯&#xff0c;那什么是一部通讯呢&#xff0c;同样的&…

gitlab(docker)安装及使用

GitLab GitLab 是一个用于仓库管理系统的开源项目&#xff0c;使用Git作为代码管理工具&#xff0c;并在此基础上搭建起来的Web服务。 下载(docker) 查询docker镜像gitlab-ce gitlab-ce是它的社区版 [rootlocalhost ~]# docker search gitlab-ce NAME …

OpenCV基本图像处理操作(六)——直方图与模版匹配

直方图 cv2.calcHist(images,channels,mask,histSize,ranges) images: 原图像图像格式为 uint8 或 float32。当传入函数时应 用中括号 [] 括来例如[img]channels: 同样用中括号括来它会告函数我们统幅图 像的直方图。如果入图像是灰度图它的值就是 [0]如果是彩色图像 的传入的…

SETR——Rethinking系列工作,展示使用纯transformer在语义分割任务上是可行的,但需要很强的训练技巧

题目:Rethinking Semantic Segmentation from a Sequence-to-Sequence Perspective with Transformers 作者: 开源:https://fudan-zvg.github.io/SETR 1.研究背景 1.1 为什么要研究这个问题? 自[ 36 ]的开创性工作以来,现有的语义分割模型主要是**基于全卷积网络( FCN )的…

ubuntu20.04安装+ros-noetic安装+内网穿透frp

刷机后的系统安装 ubuntu20.04安装安装ros-noetic安装各种必要的插件安装vscode内网穿透连接实验室主机配置frpc和frps文件运行完成自动化部署免密登录linux的免密登录windows上的免密登录 内网穿透的参考链接&#xff1a;如何优雅地访问远程主机&#xff1f;SSH与frp内网穿透配…

Python学习笔记 - 正则表达式

前言 正则表达式&#xff08;Regular Expression&#xff0c;在代码中常简写为 regex、regexp、RE 或 re&#xff09;是预先定义好的一个“规则字符串”&#xff0c;通过这个“规则字符串”可以匹配、查找、替换那些符合“规则”的文本&#xff0c;也就是说正则表达式针对的目标…