leetcode每日一练：链表OJ题

链表经典算法OJ题

1.1 移除链表元素

题目要求：

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 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
输出：[]

解题思路：

思路1：

定义两个指针，一个指向当前节点，一个指向当前节点的下一个节点，如果下一个节点是要删除的节点就将当前节点的next存储下一个节点的再下一个节点的地址，然后free那个节点。知道遍历完原链表，该思路是改变原链表。

思路2：

建立一个新的链表，遍历原链表，将原链表中的非删除节点给新的链表，遍历结束后新链表中没有要删除节点。

struct ListNode{
    int val;
    struct ListNode *next;
};
struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* Newhead, * NewTail;//一个头链表，一个链表尾部
    Newhead = NewTail = NULL;
    //遍历原链表
    struct ListNode* pcur = head;
    while (pcur){
        if (pcur->val != val){
            if (Newhead == NULL){
                Newhead = NewTail = pcur;
            }
            else{
                NewTail->next = pcur;
                NewTail = NewTail->next;
            }
        }
        pcur = pcur->next;
    }
    //如果要删除值在原链表为节点,新链表的尾节点就不会指向NULL，所以这里要判断
    if (NewTail){
        NewTail->next = NULL;
    }
    return Newhead;
}

1.2 反转链表

题目要求：

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

示例 1：

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

示例 2：

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

示例 3：

输入：head = []
输出：[]

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

解题思路：

可以定义三个新的节点类型的指针变量n1、n2、n3。然后就可以使用这三个指针来反转链表。首先n1初始化为NULL，n2初始化为head链表头结点，n3则是head头结点的下一个节点。然后循环n2->next = n1， n1 = n2， n2 = n3，n3 = n3->next。循环往复就完成了反转链表的操作。

typedef struct ListNode{
    int val;
    struct ListNode *next;
}*pList;

//反转链表函数实现
pList reverselist(pList head){
    if (head == NULL){
        return NULL;
    }
    pList n1, n2, n3;
    n1 = NULL, n2 = head, n3 = head->next;
    while (n2){
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)//如果n3为NULL就不再向后访问了
           n3 = n3->next;
    }
    return n1;
}

//以下调用上面函数的main是我自己写的，可以供大家参考
int main()
{
    //创建链表
    struct ListNode* phead, *pTail, *p;
    phead = pTail = NULL;
    int n = 0;
    printf("请输入要创建链表节点个数:>");
    scanf("%d", &n);
    int i = 0;
    for (i = 0; i < n; i++)
    {
        p = (pList)malloc(sizeof(struct ListNode));
        printf("请输入第%d个节点的值:>", i + 1);
        scanf("%d", &(p->val));
        p->next = NULL;
        if (phead == NULL)
        {
            phead = p;
            pTail = phead;
        }
        else
        {
            pTail->next = p;
            pTail = pTail->next;
        }
    }
    //调用反转链表函数
    pList Newhead = reverselist(phead);
    if (Newhead == NULL)
    {
        perror("reverselist");
        return;
    }
    phead = Newhead;
    //打印链表节点数据
    while (Newhead)
    {
        printf("%d->", Newhead->val);
        Newhead = Newhead->next;
    }
    printf("NULL\n");
    i = 1;
    Newhead = phead;
    //销毁链表
    while (Newhead)
    {
        phead = phead->next;
        free(Newhead);
        Newhead = phead;
        printf("已释放第%d条节点\n", i);
        i++;
    }
    return 0;
}

1.3 合并两个有序链表

题目要求：

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

示例 1：

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

示例 2：

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

示例 3：

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

解题思路：

定义两个新的节点指针，一个头节点，一个尾结点。比较两个原链表当前节点的数据大小，然后插入新的链表，知道插完为止

typedef struct ListNode {
    int val;
    struct ListNode* next;
}*pList;
//合并两个有序链表函数实现
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL){
        return list2;
    }
    if (list2 == NULL){
        return list1;
    }
    struct ListNode* cur1, *cur2;
    cur1 = list1, cur2 = list2;
    struct ListNode* phead, * pTail;
    phead = pTail = (struct ListNode*)malloc(sizeof(struct ListNode));
    while (cur1 && cur2) {
        if (cur1->val < cur2->val){
            pTail->next = cur1;
            pTail = pTail->next;
            cur1 = cur1->next;
        }
        else{
            pTail->next = cur2;
            pTail = pTail->next;
            cur2 = cur2->next;
        }
    }
    if (cur1) {
        pTail->next = cur1;
    }
    if (cur2) {
        pTail->next = cur2;
    }
    struct ListNode* retList = phead->next;
    free(phead);
    return retList;
}
//以下创建链表调用函数的代码是自己写的，只为调用上面函数，不是链表规范创建。仅供参考
int main()
{
    struct ListNode* phead1, pTail1, p1;
    struct ListNode* phead2, pTail2, p2;
    phead1 = pTail1 = NULL;
    phead2 = pTail2 = NULL;
    int n = 0;
    printf("请输入要创建p1和p2链表节点个数:>");
    scanf("%d", &n);
    int i = 0;
    for (i = 0; i < n; i++)
    {
        p1 = (pList)malloc(sizeof(struct ListNode));
        p2 = (pList)malloc(sizeof(struct ListNode));
        printf("请输入p1链表第%d个节点的值:>", i + 1);
        scanf("%d", &(p1->val));
        printf("请输入p2链表第%d个节点的值:>", i + 1);
        scanf("%d", &(p2->val));
        p1->next = NULL;
        p2->next = NULL;
        if (phead1 == NULL && phead2 == NULL)
        {
            phead1 = p1;
            pTail1 = phead1;
            phead2 = p2;
            pTail2 = phead2;
        }
        else
        {
            pTail1->next = p1;
            pTail1 = pTail1->next;
            pTail2->next = p2;
            pTail2 = pTail2->next;
        }
    }
    pList Newhead = mergeTwoLists(phead1,phead2);
    if (Newhead == NULL)
    {
        perror("reverselist");
        return;
    }
    pList phead = Newhead;
    while (Newhead)
    {
        printf("%d->", Newhead->val);
        Newhead = Newhead->next;
    }
    printf("NULL\n");
    i = 1;
    Newhead = phead;
    while (Newhead)
    {
        phead = phead->next;
        free(Newhead);
        Newhead = phead;
        printf("已释放第%d条节点\n", i);
        i++;
    }
    return 0;
}

1.4 链表的中间节点

题目要求：

给你单链表的头结点 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 ，返回第二个结点。

解题思路：

快慢指针：使用快慢指针来遍历链表，慢指针每次走一步，快指针每次走两步，当快指针走到最后慢指针刚好走到中间节点。因为快指针是慢指针的2倍。所以快指针从起点到终点时慢指针就是这个路程的一半，是中点。

typedef struct ListNode{
    int val;
    struct ListNode* next;
}*pList;
//函数实现
struct ListNode* middleNode(struct ListNode* head) {
    if (head == NULL){
        return NULL;
    }
    struct ListNode* slow, *fast;
    slow = fast = head;
    //节点数可能是奇数个也可能是偶数个，所以要两种判断
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

1.5 环形链表的约瑟夫问题

著名的Josephus问题

据说著名的历史学家 Josephus有过以下的故事：故事据说发生在古罗马时期，在罗马人占领乔塔帕特后，39个犹太人与约瑟夫及他的朋友躲到一个洞中，他们宁愿死也不要被敌人抓到，于是约定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下1个人重新报数，直到所有人都自杀身亡为止。

然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

题目要求：

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

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

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

数据范围： 1≤𝑛,𝑚≤100001≤n,m≤10000

进阶：空间复杂度 𝑂(1)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* ListBuyNode(int val)
{
    ListNode* ret = (ListNode*)malloc(sizeof(ListNode));
    if(ret==NULL)
    {
        perror("malloc");
        return NULL;
    }
    ret->val = val;
    ret->next = NULL;
    return ret;
}
//创建一个环形链表并返回
ListNode* CreatNode(int n)
{
    ListNode* phead = ListBuyNode(1);
    ListNode* pTail = phead;
    int i = 0;
    for(i=2;i<=n;i++)
    {
        pTail->next = ListBuyNode(i);
        pTail = pTail->next;
    }
    pTail->next = phead;//将链表循环
    return pTail;
}

int ysf(int n, int m ) {
    // write code here
    ListNode* prev = CreatNode(n);
    ListNode* cur = prev->next;
    int count = 1;
    //遍历判断
    while(cur->next!=cur){
        if(count == m){
            prev->next = cur->next;
            free(cur);
            cur = prev->next;
            count = 1;
        }
        else{
            prev = cur;
            cur = cur->next;
            count++;
        }
    }
    return cur->val;
}

1.6 分隔链表

题目要求：

给你一个链表的头节点 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,2]

解题思路：

大小链表：我们可以创建两个新的链表，为大小链表。遍历原链表。大于等于x的节点连接在大链表，小于x的节点连接在小链表。最后将大链表的头结点连接在小链表的尾结点。返回小链表的头结点

typedef struct ListNode {
    int val;
    struct ListNode* next;
}*pList;

//分隔链表的函数实现
struct ListNode* partition(struct ListNode* head, int x) {
    if (head == NULL){
        return NULL;
    }
    struct ListNode* lessHead, * lessTail;
    struct ListNode* greaterHead, * greaterTail;
    //定义哨兵位
    lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
    greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* pcur = head;//用来遍历原链表
    //分隔操作
    while (pcur){
        if (pcur->val >= x){
            greaterTail->next = pcur;
            greaterTail = greaterTail->next;
        }
        else{
            lessTail->next = pcur;
            lessTail = lessTail->next;
        }
        pcur = pcur->next;
    }
    //将大小链表连接起来
    lessTail->next = greaterHead->next;
    if(greaterTail)
       greaterTail->next = NULL;
    //释放哨兵位
    free(greaterHead);
    struct ListNode* retList = lessHead->next;
    free(lessHead);
    //返回头结点
    return retList;
}
int main()
{
    pList phead, pTail, p;
    phead = pTail = NULL;
    int n = 0;
    printf("请输入要创建链表节点个数:>");
    scanf("%d", &n);
    int i = 0;
    for (i = 0; i < n; i++)
    {
        p = (pList)malloc(sizeof(struct ListNode));
        printf("请输入第%d个节点的值:>", i + 1);
        scanf("%d", &(p->val));
        p->next = NULL;
        if (phead == NULL)
        {
            phead = p;
            pTail = phead;
        }
        else
        {
            pTail->next = p;
            pTail = pTail->next;
        }
    }
    pList Newhead = partition(phead, 3);
    if (Newhead == NULL)
    {
        perror("reverselist");
        return;
    }
    phead = Newhead;
    while (Newhead)
    {
        printf("%d->", Newhead->val);
        Newhead = Newhead->next;
    }
    printf("NULL\n");
    i = 1;
    Newhead = phead;
    while (Newhead)
    {
        phead = phead->next;
        free(Newhead);
        Newhead = phead;
        printf("已释放第%d条节点\n", i);
        i++;
    }
    return 0;
}

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

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

相关文章

Kotlin扩展函数(also apply run let)和with函数

Kotlin扩展函数(also apply run let)和with函数

also apply run let with的使用例子 private fun testOperator() {/*** also*/val person Person("ZhangSan", 18)person.also {// 通常仅仅打印使用, 也可以通过it修改it.name "ZhangSan1"println("also inner name: " it.name)}println(&qu…
阅读更多...
如何理解MySql的MVCC机制

如何理解MySql的MVCC机制

MVCC是什么 MySQL的MVCC机制&#xff0c;全称为多版本并发控制&#xff08;Multi-VersionConcurrency Control&#xff09;&#xff0c;是一种提高数据库并发性能的技术。MVCC的主要目的是在保证数据一致性的同时&#xff0c;提高数据库的并发性能。 它通过为每个读操作创建数…
阅读更多...
lower()方法——大写字母转换为小写字母

lower()方法——大写字母转换为小写字母

自学python如何成为大佬(目录):https://blog.csdn.net/weixin_67859959/article/details/139049996?spm1001.2014.3001.5501 语法参考 lower()方法用于将字符串中的大写字母转换为小写字母。如果字符串中没有需要被转换的字符&#xff0c;则将原字符串返回&#xff1b;否则将…
阅读更多...
Hadoop-08-HDFS集群 基础知识 命令行上机实操 hadoop fs 分布式文件系统 读写原理 读流程与写流程 基本语法上传下载拷贝移动文件

Hadoop-08-HDFS集群 基础知识 命令行上机实操 hadoop fs 分布式文件系统 读写原理 读流程与写流程 基本语法上传下载拷贝移动文件

章节内容 上一节完成&#xff1a; HDFS的简介内容HDFS基础原理HDFS读文件流程HDFS写文件流程 背景介绍 这里是三台公网云服务器&#xff0c;每台 2C4G&#xff0c;搭建一个Hadoop的学习环境&#xff0c;供我学习。 之前已经在 VM 虚拟机上搭建过一次&#xff0c;但是没留下…
阅读更多...
RK3568平台（USB篇）USB HID设备

RK3568平台（USB篇）USB HID设备

一.USB HID设备简介 USB HID设备主要用于和计算机进行交互通信&#xff0c;典型的USB HID类设备包括USB键盘、USB鼠标、USB游戏手柄等等&#xff0c;这些都是日常生活中常见的设备。以USB接口的鼠标为例&#xff0c;打开计算机的“设备管理器”&#xff0c;可以在“鼠标和其他…
阅读更多...
Milvus【部署 01】向量数据库Milvus在Linux环境下的在线+离线安装

Milvus【部署 01】向量数据库Milvus在Linux环境下的在线+离线安装

向量数据库Milvus在Linux环境下的在线离线安装 1.千问简介2.在线安装2.离线安装 1.千问简介 Milvus 是一款专为处理高维向量数据设计的开源云原生数据库&#xff0c;旨在满足海量向量数据的实时召回需求。它由 Zilliz 公司开发并维护&#xff0c;基于Apache许可证2.0版本发布。…
阅读更多...
Microsoft SQL Server 2019安装和设置用户密码

Microsoft SQL Server 2019安装和设置用户密码

1、免费下载两个安装包 SQL2019-SSEI-Dev 地址:https://www.microsoft.com/en-us/sql-server/sql-server-downloads SSMS-Setup-CHS 地址:https://aka.ms/ssmsfullsetup 安装具体不在阐述了&#xff0c;可以参考我这篇文章&#xff1a;SQL Server 2019安装详细教程 2、以W…
阅读更多...
llm-universe | 五. 系统评估与优化

llm-universe | 五. 系统评估与优化

系统评估与优化 一.LLM应用评估思路1.人工评估准则一 量化评估准则二 多维评估 2.自动评估方法一. 构造客观题方法二. 计算答案相似度 3.使用大模型评估4.混合评估 二.评估并优化生成部分1. 提升直观回答质量2.标明知识来源&#xff0c;提高可信度3. 构造思维链4.增加一个指令解…
阅读更多...
springboot学习，如何用redission实现分布式锁

springboot学习，如何用redission实现分布式锁

目录 一、springboot框架介绍二、redission是什么三、什么是分布式锁四、如何用redission实现分布式锁 一、springboot框架介绍 Spring Boot是一个开源的Java框架&#xff0c;由Pivotal团队&#xff08;现为VMware的一部分&#xff09;于2013年推出。它旨在简化Spring应用程序…
阅读更多...
详解C语言分支与循环语句

详解C语言分支与循环语句

分支语句 if elseswitch 循环语句 whilefordo while goto语句 文章目录 1.什么是语句2.分支语句&#xff08;选择结构&#xff09;2.1 if语句2.1.1 悬空else2.1.3 练习 2.2 switch语句2.2.1 在switch语句中的break2.2.2 default子句 3.循环语句3.1 while循环3.1.1 while语句中…
阅读更多...
2024广州智能音箱展|广州蓝牙耳机展

2024广州智能音箱展|广州蓝牙耳机展

2024广州智能音箱展|广州蓝牙耳机展 时间&#xff1a;2024年11月29日-12月1日 地点&#xff1a;广州琶洲保利世贸博览馆 【展会简介】 中国是全球最大的音频产品制造基地和消费市场&#xff0c;随着国内外互联网巨头纷纷瞄准音频行业并投入巨资布局AI产品矩阵&#xff0c;音…
阅读更多...
Static Timing Analysis(STA)概述

Static Timing Analysis(STA)概述

文章目录 Preface一、Design Objects二、Timing Paths三、Delay Calculation1. cell delay2. net delay 四、Constraint Checks五、Timing Exceptions1. Setting false paths2. Setting Maximum and Minimum Path Delays3. Setting Multicycle Paths Summary Preface Static t…
阅读更多...
Yolov8可视化界面使用说明，含代码

Yolov8可视化界面使用说明，含代码

⭐⭐ YOLOv8改进专栏|包含主干、模块、注意力机制、检测头等前沿创新 ​ ⭐⭐ YOLOv8可视化界面如下 使用需要安装opencv-python、torch、numpy及PySide6(python版本>3.9) pip install PySide6 pip install numpy pip install opencv-python 使用说明 运行下方代码&#xf…
阅读更多...
C - Popcorn（abs358）

C - Popcorn（abs358）

题意&#xff1a;有n个摊子&#xff0c;m个爆米花&#xff0c;想花费最少去的店铺买到所有的口味的爆米花&#xff0c;找到每一列都为‘o’的最少行数。 分析&#xff1a;用dfs寻找最少路径 #include<bits/stdc.h> using namespace std; typedef long long ll; char x;…
阅读更多...
那些好用的 Vue3 的工具搭子！！【送源码】

那些好用的 Vue3 的工具搭子！！【送源码】

2020 年 9 月 18 日 Vue3 的正式发布已经过去了大约 3 年 9 个月左右&#xff01;&#xff01;&#xff01; 随着 Vue3 版本的逐渐成熟&#xff0c;我们的前端世界也迎来了一系列令人振奋的更新和工具。Vue 生态圈的持续扩大&#xff0c;无疑为前端开发人员带来了前所未有的便…
阅读更多...
【自用】CentOS7.6 安装 node-RED 4.0.2 教程（各种坑都摆脱的版本）

【自用】CentOS7.6 安装 node-RED 4.0.2 教程（各种坑都摆脱的版本）

步骤总览 1.下载安装 nodejs 2.安装并配置 node-RED 3.重启服务器&#xff0c;验证 node-RED 是否安装 and 配置成功 一、下载安装 nodejs 1.下载 nodejs 18 为什么要下载 nodejs 18 呢&#xff1f; 因为 node-RED 4.0.1 支持的最低 nodejs 版本就是 nodejs 18。 当然了&a…
阅读更多...
javaEE——Servlet

javaEE——Servlet

1.web开发概述 所谓web开发,指的是从网页中向后端程序发送请求,与后端程序进行交互 2.java后端开发环境搭建 web后端(javaEE)程序需要运行在服务器中的&#xff0c;这样前端才可以访问得到 3.服务器是什么&#xff1f; ①服务器就是一款软件&#xff0c;可以向其发送请求&#…
阅读更多...
基于Canvas的Html5多时区动态时钟实战

基于Canvas的Html5多时区动态时钟实战

目录 前言 一、关于Canvas技术 1、Canvas是什么 2、Canvas的属性及渲染特性 二、Canvas动态多时区展示 1、新建html页面 2、创建Canvas对象 3、绘制所有的时钟 总结 前言 出差旅行相信大家一定会住酒店&#xff0c;大家在酒店的前台进行预订的时候&#xff0c;是不是都…
阅读更多...
【开发篇】明明配置跨域声明，为什么却仍可以发送HTTP请求

【开发篇】明明配置跨域声明，为什么却仍可以发送HTTP请求

一、问题 在SpringBoot项目中&#xff0c;明确指定仅允许指定网站跨域访问&#xff1a; 为什么开发人员却仍旧可以通过HTTP工具调用接口&#xff1f; 二、为什么 在回答这个问题之前&#xff0c;我们首先要了解一下什么是CORS&#xff01; 1、什么是CORS CORS的全称为跨域资源…
阅读更多...
TOGAF培训什么内容？参加TOGAF培训有什么好处？考试通过率多少？

TOGAF培训什么内容？参加TOGAF培训有什么好处？考试通过率多少？

TOGAF培训什么内容&#xff1f;参加TOGAF培训有什么好处&#xff1f;考试通过率多少&#xff1f; TOGAF培训哪些内容&#xff1f; 通过本课程&#xff0c;你将掌握TOGAF的理论和实践&#xff0c;理解企业架构的影响&#xff0c;能够评估、启动、设 计、执行新一轮企业和IT架构…
阅读更多...
最新文章

Copyright @ 2022~2023