数据结构->链表分类与oj(题),带你提升代码好感

✅作者简介:大家好,我是橘橙黄又青,一个想要与大家共同进步的男人😉😉

🍎个人主页:橘橙黄又青-CSDN博客

1.🍎链表的分类

前面我们学过顺序表,顺序表问题:

  • 1. 中间/头部的插入删除,时间复杂度为O(N)
  • 2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。
  • 3. 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到 200,我们再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。

这些问题,链表给出了相应的答案。

概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。

 比如说我们前面学习的单链表就是如此。

单链表是单向不循环不带头链表

 

实际中要实现的链表的结构非常多样,以下情况组合起来就有8种链表结构:

  • 1. 单向、双向
  • 2. 带头、不带头
  • 3. 循环、非循环

又称2x2x2 

图解:

 

  • 1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
  • 2. 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都 是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带 来很多优势,实现反而简单了,后面我们代码实现了就知道了。 

2.🍎链表相关基础oj

题目链接
设计链表. - 力扣(LeetCode)
两数相加. - 力扣(LeetCode)
合并两个有序链表. - 力扣(LeetCode)
两两交换链表中的节点. - 力扣(LeetCode)
删除排序链表中的重复元素. - 力扣(LeetCode)
删除排序链表中的重复元素II. - 力扣(LeetCode)
相交链表. - 力扣(LeetCode)
移除链表元素. - 力扣(LeetCode)
回文链表. - 力扣(LeetCode)
奇偶链表. - 力扣(LeetCode)
链表的中间结点. - 力扣(LeetCode)
链表最大孪生和. - 力扣(LeetCode)
两两交换链表中的节点404: This page could not be found

合并两个链表中,可以安排一个哨兵(头)可以减少判断空的代码。

哨兵位的申请:

这些都是比较好的题目,

接下来我们分析几道题目

题目链接
反转链表. - 力扣(LeetCode)
反转链表II. - 力扣(LeetCode)
链表中间节点问题. - 力扣(LeetCode)
环形链表的约瑟夫问题环形链表的约瑟夫问题_牛客题霸_牛客网

2.1🍎第一个反转链表

第一种:头插法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 //头插术
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    ListNode* returnHead = NULL;
    ListNode* ListLt = head;
    while(ListLt != NULL){
        //保存下一个节点
        ListNode* temp = ListLt -> next;
        //换头手术
        ListLt -> next = returnHead;
        returnHead = ListLt;
        //迭代
        ListLt = temp;

    }
    return returnHead;
}

这里说一个错误代码:

输出结果为1,为什么来:

 

所以temp要保存下一个节点。 

第二种解法:

三指针法:

代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    if(head == NULL){
        return head;
    }
    ListNode* n1 = NULL;
    ListNode* n2 = head;
    ListNode* n3 = head -> next;
    ListNode* pcur = head;
    while(n2){
        n2-> next = n1;
        n1 = n2;
        n2 = n3;
        if(n3){//这里防止n3为空,如果为空就无next
            n3 = n3 -> next; 
        }
    }
    return n1;
}

图解:

链表II与这个差不多,思路更为复杂。 

2.2🍎链表中间节点问题

可以遍历链表计数除2,也可以使用双指针法

双指针法:

思路:

代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    ListNode* slow,*fast;
    slow = fast = head;
    while(fast && fast -> next){
        slow = slow -> next;
        fast = fast -> next -> next;
    }
    return slow;
}

值得注意的是循环条件不能写成 fast -> next &&fast ,原因是计算机编译器是从左往右编译的,如果fast为空,就没有fast -> next。

快慢指针法以后会经常使用务必理解.

2.3.环形链表的约瑟夫问题 

题目:

这里我们输入Li 它就有暗示,说明已经有结构体结构了

解题代码:

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param m int整型 
 * @return int整型
 */
 typedef struct ListNode ListNode;
//申请一个节点
 ListNode* BuyNode(int x){
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode -> val = x;
    newNode -> next = NULL;
    return newNode;

 }
 ListNode* creteList(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 phead;
 }
#include <stdio.h>
int ysf(int n, int m ) {
    //逢m删除节点
    ListNode* head = creteList(n);
    ListNode* pcur = head;
    //前驱节点
    ListNode* prev = NULL;
    
    int conut = 1;
    while (pcur ->next != pcur) {
        if(conut == m){
            //删除当前节点
            prev -> next = pcur ->next;
            free(pcur);
            //删除节点后往后走,让pcur走到新的位置,conut为初始值
            pcur = prev -> next;
            conut = 1;
        }
        else{
            //pcur往后走
            prev = pcur;
            pcur =  pcur -> next;
            conut++;
        }
    }
    //此时pcur节点就是活下来的节点
    return pcur -> val;
}

3.🍎上节链表代码建议重复观看

SList.c文件:

 SList.h文件

 test.c文件测试代码: 

 test.c文件代码

#include"SList.h"

//void SlistTest01() {
// 
//	链表的打印
//	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
//	node1->data = 1;
//	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
//	node2->data = 2;
//	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
//	node3->data = 3;
//	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
//	node4->data = 4;
//
//	node1->next = node2;
//	node2->next = node3;
//	node3->next = node4;
//	node4->next = NULL;
//
//	SLTNode* plist = node1;
//	SLTPrint(plist);
//}
void SlistTest02() {
	//尾插测试
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist); //1->2->3->4->NULL
	//头插测试
	//SLTPushFront(&plist, 5);
	//SLTPrint(plist);          //5->1->2->3->4->NULL
	//SLTPushFront(&plist, 6);
	//SLTPrint(plist);         //6->5->1->2->3->4->NULL
	//SLTPushFront(&plist, 7);
	//SLTPrint(plist);         //7-6->5->1->2->3->4->NULL

	SLTPopBack(&plist);
	SLTPrint(plist);//1->2->3->NULL
	SLTPopBack(&plist);
	SLTPrint(plist);//1->2->3->NULL
	SLTPopBack(&plist);
	SLTPrint(plist);//1->2->3->NULL
	SLTPopBack(&plist);
	SLTPrint(plist);//1->2->3->NULL
	SLTPopBack(&plist);
	SLTPrint(plist);//1->2->3->NULL
}

void SlistTest03() {
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist); //1->2->3->4->NULL

	SListDesTroy(&plist);


	头删
	//SLTPopFront(&plist);
	//SLTPrint(plist);    //2->3->4->NULL
	//SLTPopFront(&plist);
	//SLTPrint(plist);    //3->4->NULL
	//SLTPopFront(&plist);
	//SLTPrint(plist);    //4->NULL
	//SLTPopFront(&plist);
	//SLTPrint(plist);    //NULL
	//SLTPopFront(&plist);
	//SLTPrint(plist);    //assert
	
	//查找测试
	//SLTNode* FindRet = SLTFind(&plist, 3);
	//if (FindRet) {
	//	printf("找到了!\n");
	//}
	//else {
	//	printf("未找到!\n");
	//}
	//SLTInsert(&plist, FindRet, 100);
	//SLTInsertAfter(FindRet, 100);
	
	//删除指定位置的节点测试
	//SLTErase(&plist, FindRet);
	//SLTPrint(plist); //1->2->3->NULL
}
int main() {
	//SlistTest01();
	//SlistTest02();
	SlistTest03();
	return 0;
}

SList.c文件代码:

#include"SList.h"
//打印
void SLTPrint(SLTNode* phead) {
	SLTNode* pcur = phead;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("NULL\n");
}
//开辟空间
SLTNode* SLTBuyNode(SLTDataType x) {
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL) {
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}
//
void SLTPushBack(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
	//开辟空间
	SLTNode* newnode = SLTBuyNode(x);

	//链表为空,新节点作为phead
	if (*pphead == NULL) {
		*pphead = newnode;
		return;
	}
	//链表不为空,找尾节点
	SLTNode* ptail = *pphead;
	while (ptail->next)
	{
		ptail = ptail->next;
	}
	//ptail就是尾节点
	ptail->next = newnode;
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
	assert(pphead);
	SLTNode* newnode = SLTBuyNode(x);

	//newnode *pphead
	newnode->next = *pphead;
	*pphead = newnode;
}
//尾删
void SLTPopBack(SLTNode** pphead) {
	assert(pphead);
	//链表不能为空
	assert(*pphead);

	//链表不为空
	//链表只有一个节点,有多个节点
	if ((*pphead)->next == NULL) {
		free(*pphead);
		*pphead = NULL;
		return;
	}
	SLTNode* ptail = *pphead;
	SLTNode* prev = NULL;
	while (ptail->next)
	{
		prev = ptail;
		ptail = ptail->next;
	}

	prev->next = NULL;
	//销毁尾结点
	free(ptail);
	ptail = NULL;
}
//头删
void SLTPopFront(SLTNode** pphead) {
	assert(pphead);
	//链表不能为空
	assert(*pphead);

	//让第二个节点成为新的头
	//把旧的头结点释放掉
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}
//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x) {
	assert(pphead);

	//遍历链表
	SLTNode* pcur = *pphead;
	while (pcur) //等价于pcur != NULL
	{
		if (pcur->data == x) {
			return pcur;
		}
		pcur = pcur->next;
	}
	//没有找到
	return NULL;
}
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {
	assert(pphead);
	assert(pos);
	//要加上链表不能为空
	assert(*pphead);

	SLTNode* newnode = SLTBuyNode(x);
	//pos刚好是头结点
	if (pos == *pphead) {
		//头插
		SLTPushFront(pphead, x);
		return;
	}

	//pos不是头结点的情况
	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//prev -> newnode -> pos
	prev->next = newnode;
	newnode->next = pos;
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {
	assert(pos);

	SLTNode* newnode = SLTBuyNode(x);

	//pos newnode pos->next
	newnode->next = pos->next;
	pos->next = newnode;
}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos) {
	assert(pphead);
	assert(*pphead);
	assert(pos);

	//pos刚好是头结点,没有前驱节点,执行头删
	if (*pphead == pos) {
		//头删
		SLTPopFront(pphead);
		return;
	}

	SLTNode* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//prev pos pos->next
	prev->next = pos->next;
	free(pos);
	pos = NULL;
}
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {
	assert(pos);
	//pos->next不能为空
	assert(pos->next);

	//pos  pos->next  pos->next->next
	SLTNode* del = pos->next;
	pos->next = pos->next->next;
	free(del);
	del = NULL;
}
//销毁链表
void SListDesTroy(SLTNode** pphead) {
	assert(pphead);
	assert(*pphead);

	SLTNode* pcur = *pphead;
	while (pcur)
	{
		SLTNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

SList.h文件代码:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLTDataType;
//链表是由节点组成
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

//typedef struct SListNode SLTNode;
//打印链表
void SLTPrint(SLTNode* phead);

//链表的头插、尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);

//链表的头删、尾删
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x);

//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);

//销毁链表
void SListDesT

今天就到这里了,都看到这里了,点一个赞吧,感谢观看。

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

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

相关文章

redis IO多路复用模型详解

一、IO 1.1、IO模型 我们常说的IO&#xff0c;指的是文件的输入和输出 &#xff0c;但是在操作系统层面是如何定义IO的呢&#xff1f;到底什么样的过程可以叫做是一次IO呢&#xff1f; 拿一次磁盘文件读取为例&#xff0c;我们要读取的文件是存储在磁盘上的&#xff0c;我们的…

window环境下使用k8s部署.net core项目

前提&#xff1a;已经部署镜像到Docker 在项目发布目录下新建.yaml文件&#xff0c;内容如下&#xff08;以下仅举例出两种方式内容&#xff0c;可按需自由配置&#xff09; --方式一(创建deployment 、服务、指定命名空间) # ------------------- 注意层级结构&#xff0c;…

【debug】element-ui时间控件回显后不可编辑且显示为空

问题&#xff1a;使用element-ui的时间控件回显数据&#xff0c;编辑数据没有反应&#xff1a;点时间和“确认”按钮都没反应。 输入框中会显示数据&#xff0c;但提交时的校验显示为空。 <el-form-item label"开始时间" prop"limitStartTime"><…

激光炸弹 刷题笔记

前置知识 二维前缀和 子矩阵的和 刷题笔记 {二维前缀和}-CSDN博客 思路 参考二维前缀和 将子矩阵的和 做成动态矩阵 一个个矩阵搜索 符合要求边长 矩阵中的元素和最大值 将x1,y1用i-k,j-k表示即可 x2,y2用i&#xff0c;j表示 代码 #include<iostream> #include<…

【定岗定编】某度假村酒店客房部定岗定编管理咨询项目纪实

该度假村酒店由于地域广阔&#xff0c;将客服部分为了四个不同区域&#xff0c;这样就导致了在不同的区域员工的接待量不均衡的状况&#xff0c;引起了员工的强烈不满。如何合理地配置客户部人员以及如何合理地鉴定员工的工作量成为该酒店所面临的两大难题。让我们来看看在人力…

【Linux】软件包管理器yum

目录 一、yum是什么&#xff1f; 二、查看软件包 三、安装与卸载软件 1、如何安装软件 2、如何卸载软件 四、yum源的配置 一、yum是什么&#xff1f; 在Linux下安装软件, 一个通常的办法是下载到程序的源代码, 并进行编译, 得到可执行程序. 但是这样太麻烦了, 于是有些人…

2024作品集流行封面设计技巧

本期不是关于如何安排作品集&#xff0c;而是关于目前国内市场上流行的作品集封面风格有哪些&#xff1f;如何实现&#xff1f;今天给大家带来了 5 种作品集设计风格&#xff0c;毛玻璃、弥散光、3D、插画、其他&#xff0c;一起往下看吧&#xff01; 毛玻璃 目前许多设计师都…

学习统一的Hyper - network用于多模态MR图像合成和缺失模态的肿瘤分割

Learning Unified Hyper-Network for Multi-Modal MR Image Synthesis and Tumor Segmentation With Missing Modalities Learning Unified Hyper-Network for Multi-Modal MR Image Synthesis and Tumor Segmentation With Missing Modalities背景贡献实验方法多模态合成方法超…

软件测试实战,Web项目网页bug定位详细分析总结(详全)

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 1、前置条件 1&a…

3.5日常学习

matlab处理数据 自己写了关于detect_data的函数&#xff0c;让它帮我改了&#xff0c;哈哈哈 %改正前function data_chuli(path1,savepath)[num]xlsread(path1,1,B18:F23);a num;ba;cb(:);xlswrite(savepath,c) end%改正后function data_chuli(path1, savepath)num xlsread…

05-调用API

上一篇&#xff1a; 04-JNI函数 调用 API 允许软件供应商将 Java VM 加载到任意本地应用程序中。供应商可以提供支持 Java 的应用程序&#xff0c;而无需链接 Java VM 源代码。 5.1 概述 下面的代码示例说明了如何使用调用 API 中的函数。在这个示例中&#xff0c;C 代码创建了…

鸿蒙NEXT开发实战:【视频文件裁剪】

使用OpenHarmony系统提供的ffmpeg三方库的能力在系统中实现了音视频文件裁剪的功能&#xff0c;并通过NAPI提供给上层应用调用。 基础信息 视频文件裁剪 简介 在OpenHarmony系统整个框架中有很多子系统&#xff0c;其中多媒体子系统是OpenHarmony比较重要的一个子系统&#…

selenium爬取空气质量数据

https://www.aqistudy.cn/ 爬取指定城市在指定时间范围内的空气质量数据&#xff0c;并将数据保存为CSV文件。它首先从两个文本文件中读取城市信息和代理IP信息&#xff0c;然后提示用户输入爬取的起始年份、结束年份、起始月份和结束月份。接下来&#xff0c;它启动了Chrome浏…

【Leetcode】3028.边界上的蚂蚁

题目描述 思路 题目中要求我们返回 蚂蚁返回到边界的次数。简单来想&#xff0c;就是蚂蚁原来的位置的一维坐标为0&#xff0c;然后经过&#xff0c;若干次移动&#xff0c;统计有几次坐标再次变为0的个数。 我们利用前缀和&#xff0c;像定义一个数组&#xff0c;算出前缀和数…

华为交换机vlan实验

一、目标 实现不同vlan之间的终端通信 二、命令学习 1.创建2个vlan # 进入系统视图 sy# 创建vlan vlan 10 vlan 202.查看vlan # 2.查看vlan display vlanThe total number of vlans is : 3 ---------------------------------------------------------------------------…

如何选择阿里云服务器配置?(CPU/内存/带宽/磁盘)

阿里云服务器配置怎么选择&#xff1f;CPU内存、公网带宽和系统盘怎么选择&#xff1f;个人开发者或中小企业选择轻量应用服务器、ECS经济型e实例&#xff0c;企业用户选择ECS通用算力型u1云服务器、ECS计算型c7、通用型g7云服务器&#xff0c;阿里云服务器网aliyunfuwuqi.com整…

Python入门教程(非常详细)从零基础入门到精通,看完这一篇就够了

前言 本文罗列了了python零基础入门到精通的详细教程&#xff0c;内容均以知识目录的形式展开。 第一章&#xff1a;python基础之markdown Typora软件下载Typora基本使用Typora补充说明编程与编程语言计算机的本质计算机五大组成部分计算机三大核心硬件操作系统 第二章&…

米哈游排名首超腾讯,登顶榜首 !!!

米哈游排名首超腾讯&#xff0c;登顶榜首 &#xff01;&#xff01;&#xff01; 大家好&#xff0c;我是銘&#xff0c;全栈开发程序员。 近日&#xff0c;第三方机构 data.ai 公布 2023 年中国游戏厂商及应用出海收入 30 强。 其中米哈游超越腾讯&#xff0c;首次登顶年度…

SDM450核心板_高通SDM450安卓核心板模块性能参数

高通SDM450核心板是基于SDM450移动平台开发的一款高性能核心板。采用领先的14纳米技术&#xff0c;该核心板为高端智能设备提供了卓越的性能和优质的体验。板载2GB16GB的内存(可选配4GB32GB)&#xff0c;双 ISP(图像传感器处理器)支持丰富的照片细节和双摄像头体验&#xff0c;…

Android大厂高级面试题灵魂100问,知识点总结+面试题解析

前言 互联网创业从火热到“寒冷”&#xff0c;但有一件事一直没变&#xff0c;就是大家都觉得招聘不到程序员。优秀的程序员也觉得很难找到合适的岗位。 “2020年技术没有成长&#xff0c;我今年一定要好好努力学习&#xff01;” “在现在这个公司都工作了3年了&#xff0c;一…