数据结构算法题(力扣)——链表

以下题目建议大家先自己动手练习,再看题解代码。这里只提供一种做法,可能不是最优解。

1. 移除链表元素(OJ链接)

题目描述:给一个链表的头节点 head 和一个整数 val ,删除链表中所有满足值等于 val 的节点,并返回新的头节点

解法:遍历链表,依次比对结点的值和val是否相等,相等则删除,不相等则更新指针指向,继续遍历。

这里需要分两种情况来讨论,一是链表结点的值都等于val,二是链表结点的值不都等于val。

struct ListNode* removeElements(struct ListNode* head, int val) 
{
    //全部结点的值都等于val或前面部分结点相等
    while(head&&head->val==val)
    {
        head=head->next;
    }
    //删除全部结点后head为空或者链表本身就为空链表
    if(!head)
    {
        return NULL;
    }
    
    struct ListNode* cur=head;
    while(cur->next)
    {
        //cur的下一个结点值等于val,则删除下一个
        if(cur->next->val==val)
        {
            cur->next=cur->next->next;
        }
        //不相等则cur后移一步
        else
        {
            cur=cur->next;
        }
    }
    return head;
}

无论链表结点中是什么样的值,当进行完第一个while循环后,如果head不是NULL,那么我们定义的cur指针指向的结点的值一定不等于val。因此第二个while循环里if的判断条件为cur->next->val==val,这样不需要保留cur的前一个结点,因为cur本身就是前一个结点(可能删除的结点的前一个结点)。

2. 反转链表(OJ链接)

题目描述:给定单链表的头节点 head ,反转链表,并返回反转后的链表的头节点。

我们所要做的操作如下图
在这里插入图片描述
如果链表为NULL,直接返回空即可。链表不为空,则需要反转。

以上图链表为例本题解法如下图所示。
在这里插入图片描述

当n2为空时,循环结束。

题解代码如下

struct ListNode* reverseList(struct ListNode* head)
{
  if(head==NULL)
  {
    return NULL;
  }
  struct ListNode* prev=NULL;
  struct ListNode* cur=head;
  struct ListNode* next=head->next;
  while(cur!=NULL)
  {
    cur->next=prev;
    prev=cur;
    cur=next;
    if(next)
    {
        next=next->next;
    }
  }
  return prev;
}

注意题解中的prev,cur和next指针分别对应图中的n1,n2,n3。最后一步时n3为NULL,所以需要加判断语句。

3. 链表的中间结点(OJ链接)

题目描述:给定单链表的头结点 head ,请你找出并返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。

如果链表结点个数为奇数,返回中间结点,如果结点数为偶数,返回第二个结点。比如有六个结点,则返回第四个结点。

解法:快慢指针法。指的是一个指针走的步数多,一个指针走的步数少。此题快指针走两步,慢指针走一步。当快指针走到NULL或最后一个结点时(链表结点数为偶数或奇数),慢指针指向的结点即为中间结点。

题解代码如下

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* fast=head,*slow=head;
    while (fast!=NULL&&fast->next!=NULL)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}

4. 合并两个有序链表(OJ链接)

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

解法:创建两个指针变量分别指向两个链表的头,依次比较结点的值,值小的结点链接到新链表的尾,依次遍历链表,其中一个链表走完后,将剩余的链表链接到新链表的尾即可。

示例:
在这里插入图片描述
题解代码如下

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (!list1) 
    {
        return list2;
    }
    if (!list2) 
    {
        return list1;
    }
    //分别指向两个链表的头结点
    ListNode *p1 = list1, *p2 = list2;
    //phead为新链表的头,ptail为新链表的尾
    ListNode *phead = NULL, *ptail = NULL;
    //两个链表都没有遍历完
    while (p1 && p2) 
    {
        if (p1->val < p2->val) 
        {
            //链接的是第一个结点
            if (phead == NULL) 
            {
                phead = ptail = p1;
                p1 = p1->next;
            } 
            else 
            {
                ptail->next = p1;
                ptail = ptail->next;
                p1 = p1->next;
            }
        } 
        else 
        {
            //链接的是第一个结点
            if (phead == NULL) 
            {
                phead = ptail = p2;
                p2 = p2->next;
            } 
            else 
            {
                ptail->next = p2;
                p2 = p2->next;
                ptail = ptail->next;
            }
        }
    }
    //链表1没有走完
    if (p1) 
    {
        ptail->next = p1;
    }
    //链表2没有走完
    if (p2) 
    {
        ptail->next = p2;
    }
    return phead;
}

5. 返回倒数第k个结点(OJ链接)

题目描述:给定一个单链表的头结点(head),找出单向链表中倒数第 k 个节点。返回该节点的值。

此题和第三题类似。解法依旧是快慢指针法

解法:快指针先走k步,然后和慢指针一起走,快指针走到NULL时,慢指针指向的结点就是倒数第k个结点。
原理:快指针先走k步,使得两个指针间隔为k。再一起以相同速度走,最后两个指针间隔依旧是k

题解代码如下

int kthToLast(struct ListNode* head, int k)
{
    struct ListNode* fast=head,*slow=head;
    while(k--)
    {
        fast=fast->next;
    }
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow->val;
}

这里就先介绍这五个题的做法,大家可以试试用别的做法看是否可以做出来噢。

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

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

相关文章

954: 单链表的链接

学习版 【c语言】 【C艹】 #include<iostream>class LinkedList { public:struct LinkedNode {char val;LinkedNode* next;LinkedNode(char val) :val(val), next(NULL) {};};LinkedList(){dummyHead new LinkedNode(0);tail dummyHead;}~LinkedList() {while (dummy…

初探STM32f407VET6

一、买到了板子&#xff0c;自己分析引脚功能 我在某宝上买到一块stm32f407vet6的板子&#xff0c;图便宜&#xff0c;结果遇上了个态度差的客服。没有说明&#xff0c;没有资料。不能退换&#xff0c;只能自己想办法分析引脚 在嘉里创找到了芯片原理图&#xff08;LQFP-100封…

【智能排班系统】快速消费线程池

文章目录 线程池介绍线程池核心参数核心线程数&#xff08;Core Pool Size&#xff09;最大线程数&#xff08;Maximum Pool Size&#xff09;队列&#xff08;Queue&#xff09;线程空闲超时时间&#xff08;KeepAliveTime&#xff09;拒绝策略&#xff08;RejectedExecutionH…

Python学习笔记-Flask接收post请求数据并存储数据库

1.引包 from flask import Flask, request, jsonify from flask_sqlalchemy import SQLAlchemy 2.配置连接,替换为自己的MySQL 数据库的实际用户名、密码和数据库名 app Flask(__name__) #创建应用实列 app.config[SQLALCHEMY_DATABASE_URI] mysqlpymysql://ro…

微软文本转语音和语音转文本功能更新,效果显著!

今天我要和大家分享一个新功能更新——微软的文本转语音和语音转文本功能。最近&#xff0c;微软对其AI语音识别和语音合成技术进行了重大升级&#xff0c;效果非常好&#xff0c;现在我将分别为大家介绍这两个功能。 先来听下这个效果吧 微软文本转语音和语音转文本功能更新 …

二分答案(砍树,借教室)

二分的两种情况附代码&#xff1a; 二分查找条件&#xff1a;单调&#xff0c;二段性 例题1&#xff1a;P1873 [COCI 2011/2012 #5] EKO / 砍树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 上代码&#xff1a; #include<bits/stdc.h> using namespace std; const …

【数据结构与算法】归并排序(详解:递归与非递归的归并排序 | 赠:冒泡排序和选择排序)

前言 本篇博客会对排序做一个收尾&#xff0c;将最经典的七大排序介绍完毕。 这次的重点正如标题&#xff0c;主要讲的是归并排序&#xff0c;还会带过相对简单很多的冒泡排序和选择排序。在最后还会给这七大排序做出一个时间复杂度和稳定性展示的总结收尾。同时&#xff0c;这…

钉钉事件订阅前缀树算法gin框架解析

当钉钉监测到发生一些事件&#xff0c;如下图 此处举例三个事件user_add_org、user_change_org、user_leave_org&#xff0c;传统的做法是&#xff0c;我们写三个if条件&#xff0c;类似下图 这样字符串匹配效率比较低&#xff0c;于是联想到gin框架中的路由匹配算法&#xff0…

非写代码无以致远

标题党一下&#xff0c;本篇文章主要汇总了一些代码题&#xff0c;让大家写一些代码练习一下吧&#xff01; 变种水仙花_牛客题霸_牛客网 (nowcoder.com) #include<stdio.h> int main() {for (int i 10000; i < 99999; i) {int sum 0;for (int j 10; j < 1000…

码农失业倒计时?全球首个大厂AI程序员来了

进入互联网时代&#xff0c;程序员作为高收入职业的代表&#xff0c;长久以来一直是众多求职者梦寐以求的工作方向。程序员们凭借其对计算机科学的深刻理解和技术创新能力&#xff0c;不仅推动了科技的进步&#xff0c;也为自己赢得了可观的经济回报。 然而&#xff0c;随着人…

AD20全流程的使用笔记

目录 首先一个完整的AD工程文件需要我们自己建立的文件有这些&#xff1a; 新建工程&#xff1a; 从现有的工程文件中将元件添加到原理图库&#xff1a; 元件的摆放&#xff1a; 器件的复制及对齐&#xff1a; 导线、Netlabe、端口的添加&#xff1a; Value值的校对&…

可视化大屏 - 项目1

文章目录 技术栈echarts 可视化需求分析代码实现 技术栈 flexible.js rem 实现不同终端下的响应式布局&#xff0c;根据不同屏幕宽度&#xff0c;自适配布局&#xff1b; html中引入index.js&#xff0c;可以改名为flexible.js&#xff1b;默认划分10份&#xff0c;可以自己修…

HarmonyOS 应用开发之TaskPool和Worker的对比 (TaskPool和Worker)

TaskPool&#xff08;任务池&#xff09;和Worker的作用是为应用程序提供一个多线程的运行环境&#xff0c;用于处理耗时的计算任务或其他密集型任务。可以有效地避免这些任务阻塞主线程&#xff0c;从而最大化系统的利用率&#xff0c;降低整体资源消耗&#xff0c;并提高系统…

日期专题:做题笔记 (时间显示/星期计算/星系炸弹/第几天/纪念日)

目录 时间显示 代码 星期计算 代码 星系炸弹 代码 第几天 纪念日 代码 时间显示 时间显示 这道题主要是单位换算。 ①单位换算 ②输出格式&#xff1a; a. 不足两位补前导零。利用printf输出 b. 注意 long long 输出格式应该是 %lld 长整型 代码 #include <…

Day66-企业级防火墙iptables精讲2

Day66-企业级防火墙iptables精讲2 1. iptables项目案例2&#xff1a;局域网共享上网&#xff1a;2. iptables项目案例3&#xff1a;外网IP的端口映射到内网IP的端口3. 老男孩教育iptables项目案例4&#xff1a;IP一对一映射&#xff08;DMZ&#xff09;4. 老男孩教育iptables项…

Java常用类和基础API

文章目录 1. 字符串相关类之不可变字符序列&#xff1a;String1.1 String的特性1.2 String的内存结构1.2.1 概述1.2.2 练习类型1&#xff1a;拼接1.2.3 练习类型2&#xff1a;new1.2.4 练习类型3&#xff1a;intern() 1.3 String的常用API-11.3.1 构造器1.3.2 字符串对象的比较…

【THM】Protocols and Servers(协议和服务器)-初级渗透测试

介绍 这个房间向用户介绍了一些常用的协议,例如: HTTP协议文件传输协议POP3邮件传输协议IMAP每个协议的每个任务都旨在帮助我们了解底层发生的情况,并且通常被优雅的GUI(图形用户界面)隐藏。我们将使用简单的 Telnet 客户端来使用上述协议进行“对话”,以充分了解GUI客户…

Unity开发一个FPS游戏之三

在前面的两篇博客中&#xff0c;我已实现了一个FPS游戏的大部分功能&#xff0c;包括了第一人称的主角运动控制&#xff0c;武器射击以及敌人的智能行为。这里我将继续完善这个游戏&#xff0c;包括以下几个方面&#xff1a; 增加一个真实的游戏场景&#xff0c;模拟一个废弃的…

5.2 通用代码,数组求和,拷贝数组,si配合di翻转数组

5.2 通用代码&#xff0c;数组求和&#xff0c;拷贝数组&#xff0c;si配合di翻转数组 1. 通用代码 通用代码类似于一个用汇编语言写程序的一个框架&#xff0c;也类似于c语言的头文件编写 assume cs:code,ds:data,ss:stack data segmentdata endsstack segmentstack endsco…

刘小光本就疑心赵本山与他媳妇李琳有染,赵本山为证实清白便想起蛋糕上的字,结果呢?

刘小光本就疑心赵本山与他媳妇李琳有染&#xff0c;赵本山为证实清白便想起蛋糕上的字&#xff0c;结果呢&#xff1f; ——小品《生日快乐》&#xff08;中5&#xff09;的台词 &#xff08;接上&#xff09; 赵本山&#xff1a;噢!对对!那谁&#xff0c;老四&#xff0c;是…