阅读量:0
1.线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使 ⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。
具有一类相同特性的数据结构的集合
水果：苹果、香蕉、梨
蔬菜：青菜、黄瓜、冬瓜、丝瓜
线性表：顺序表、链表
具有一类相同特性的数据结构的集合
想用特征指的是两个方面：逻辑结构、物理结构
那么物理结构指的是数据在内存上的存储形式
逻辑结构：人为想象出来的数据的组织形式
线性表中的成员在逻辑结构上都是线性的
对于一个数组1 2 3 4 5 6
下标i进行++操作依次访问，这个可以看得出数组在物理结构上是线性的
因为这个数组的排列顺序我们能知道数组在逻辑结构上面的话是线性的
而对于顺序表来说，逻辑结构是线性的，但是物理结构是不是线性的呢
所以顺序表在逻辑结构上一定是线性表，但是在物理结构上我们不知道是不是线性的
我们需要对顺序表的底层结构进行探究
2.顺序表
顺序表的基础概念
顺序表的概念:顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组存储
所以顺序表的底层结构就是数组
我们在上一章节说道：顺序表在逻辑结构上一定是线性表，但是在物理结构上我们不知道是不是线性的
但是这里我们知道顺序表的底层结构是数组，因为数组在物理结构上是线性的，那么顺序表在物理结构上也是线性的
那么数组和顺序表的区别是什么呢？
将数组进封装一下，提供一些对数据管理的操作，比如说增加删除修改查找
那么数组就变成了顺序表，所以说顺序表的底层结构是数组
顺序表是对数组进行封装：结构体
顺序表的定义
定义之前已经知道数组大小的数组
int arr[3]={1,2,3}
定义之前不知道数组大小的数组---动态内存管理
int *arr---定义一个指针
sequence:流畅的 List:表
那么对顺序表的定义
静态顺序表的定义
1.已知顺序表的大小:
静态顺序表：
struct SeqList
{
int arr[1000];
int size;//顺序表中有效数据的个数
}；
如果我们一开始不知道顺序表的大小的话，在后面代码生成的时候申请了大小，这就是动态顺序表
对于顺序表，我们不一定是整型数组，可能是字符数组，那么这个时候我们就要用到typedef了，将数据类型重命名，因为这样会很方便的，如果一个个改的话就很麻烦
我们在不确定用什么类型的数据的时候，我们将数据类型重命名就行了，到时候我们要进行更改的时候仅仅只需要更改这里的数据类型，没必要一个个进行更改
那么上面的顺序表就改成这个样子了
typedef int SLDataType
define N 7 我们在这里将数组的大小进行宏定义，随时可以进行修改的
struct SeqList
{
SLDataType arr[N];
int size;//顺序表中有效数据的个数
}；
以后不想使用整型的数据就将一开始的重命名进行修改就行了
动态顺序表的定义
对于动态的顺序表的话，我们不知道数组的大小
struct SeqList
{
int *arr; 我们在这里创建一个指针，后期我们为这块指针指向的空间申请空间
int capacity； 顺序表空间大小，我们需要一个变量来保存我们的空间大小
int size;//顺序表中有效数据的个数
int size;//保存当前顺序表有效数据的个数
}；
静态顺序表和动态顺序表的对比以及优缺点
那么我们到这里就知道了顺序表分为动态和静态的，但是哪个好呢？
对于静态顺序表，我们必须知道顺序表的大小，我们要给定一个大小‘
对于这个数组大小我们是不好定义的
假设我们一开始给的大小是100，但是后期我们要插入10000，那么很明显空间不够用，那么会造成空间数据丢失，会有很严重的后果的
如果我们给的顺序表大小很大，但是利用率很低，就会造成空间的浪费了
那么我们总结一下静态顺序表的缺点：
空间给小了不够用，给大了造成空间浪费
对于动态顺序表来说的话，我们一开始用malloc开辟一块空间，如果后期所需的空间不够的话，我们是可以用reallocJ进行空间大小扩增的，我们再次申请一块空间了，即是这个动态顺序表在开辟空间是造成了浪费，那么这个浪费也是可控的，浪费程度比较小
对比了两种顺序表，明显是动态顺序表更加好些，那么我们接下来实现动态顺序表
动态顺序表的实现
我们在实现顺序表的时候我们需要三个文件个文件 SeqList.c和SeqList.h和test.c文件
我们在SeqList.c中具体实现各种操作
我们在SeqList.h中定义顺序表结构，声明要提供的操作
我们在test.c文件中主要是对我们我们写的顺序表进行测试，看看写的对不对，测试函数
.h文件就起到了目录的作用，主要放的是函数的名称
.c文件就起到了对函数的具体操作
#define _CRT_SECURE_NO_WARNINGS 1 #include "SeqList.h" void SLtest01() { SL s;//创建顺序表变量 SLInit(&s);//我们这里初始化应该传的是地址，而不是值,//如果传的是值，那么sl的改变会影响s的改变 //尾插数据 SLPushBack(&s, 1); SLPushBack(&s, 2); SLPushBack(&s, 3); SLPushBack(&s, 4); SLPrint(&s); /*SLPushFront(&s, 1); SLPushFront(&s, 2); SLPushFront(&s, 3); SLPushFront(&s, 4); SLPrint(&s); SLInsert(&s, 12, s.size-1); SLPopBack(&s);*/ //删除指定位置数据 /*SLErase(&s, s.size-1); SLPrint(&s);*/ int ret=SLFind(&s, 2); printf("%d", ret); SLDestory(&s); } int main() { SLtest01(); return 0; } #define _CRT_SECURE_NO_WARNINGS 1 #include "SeqList.h" //顺序表的初始化 void SLInit(SL *ps) { ps->arr = NULL; ps->size = ps->capacity = 0; } //顺序表的销毁 void SLDestory(SL *ps) { if (ps->arr )//相当于ps!=NULL { free(ps->arr);//将申请的空间进行释放 } //让变量回到最初始的状态 ps->arr = NULL; ps->size = ps->capacity = 0; } /*对于插入数据，有两种情况：空间充足和空间不足 空间充足：顺序表的容量为capacity，有效数据为size个， 那么我们只需要在顺序表的下标为size的位置进行插入数据，然后进行size++，插入其他的数据 空间不足：先增容，再插入。一但capacity=size时，就说明我们的顺序表满了，那么我们就进行增容操作 所以我们在插入数据的时候要先判断空间是否充足*/ /*增容的讲究 * 增容一般是成倍数的增加，比如2 3倍 * 为什么不能一次增容到位呢？ 因为增容的操作本身就有一定的程序性能的消耗，若频繁的增容会 导致程序效率低下 */ /*增容分两种情况 * 1.连续空间足够，直接扩容 * 2.连续空间不够 （1）要重新找一块满足条件的地址，分配足够的内存 * （2）拷贝原有的数据到新的地址 * （3）销毁地址 增量和插入数据的个数是正相关的，所以我们每次采用二倍进行增容 */ //判断空间是否充足 void SLCheckCapacity(SL*ps) { //判断空间是否充足 if (ps->size == ps->capacity)//空间不足，我们要进行增容操作 {//有效数据等于实际容量，就是说明当前内存已经满了 //增容 //我们要将realloc返回的地址强转为SLDatatype* //因为顺序表中数据类型都是SLDatatype //为了防止申请失败的话，返回的是NULL，原有的数据都消失了 //我们创建一个临时变量，在进行判断是否申请成功了，我们再为原先的地址进行付赋值 //我们要对capacity进行判断，如果capacity一开始是0的话，那么增容的结果还是0 //所以我们在增容之前要对capacity进行判断 //若capacity为.，给个默认值，否则x2倍 int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; /*解释下这个三目操作符 * 如果ps->capacity == 0的话，那么我们就给一个默认值4 * 如果ps->capacity ！= 0的话，那么我们直接给容量乘个2倍 之所以乘以二，我们将这个乘以二的值直接放到增容的参数里面， 原先的参数就是二倍的capacity 但是现在的参数newCapacity同样也是2倍的 */ SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));//2倍的增加 //判断是否申请成功 我们的容量还要乘以每个元素的字节大小就是我们要申请的空间大小 if (tmp == NULL) //如果这里是整型的话，那么我们就要申请4个整型大小的空间，每个整型4个字节 { perror("realloc fail!"); exit(1);//都申请失败了，我们直接退出 } //增容成功 ps->arr = tmp; ps->capacity = newCapacity; } } //时间复杂度为O(1) //尾部插入数据 void SLPushBack(SL* ps, SLDatatype x)//往哪里插入数据，插入的数据是什么 { //判断传过来的地址是不是空地址 /*if (ps == NULL) { return; }*/ //粗暴的解决方法 assert(ps);//等价于assrert(pa!=NULL) //如果ps为空指针那么就会报错 //判断空间是否充足 SLCheckCapacity(ps); //插入数据 //我们直接在下标为size的位置进行插入数据 //插入完数据之后我们进行size++操作，进行下个数据的插入 ps->arr[ps -> size++] = x; //换另一个位置进行插入数据 } /*对于头插操作 * 我们需要将一个数字插到第一个 * 在之前我们需要将原本的数字往后面挪动一位 * 从后往前进行挪动 * 如果从前往后会导致数据被覆盖的 * 挪动完成之后我们再为第一个数进行赋值 */ //时间复杂度为O(N) //头部插入数据 void SLPushFront(SL* ps, SLDatatype x) { //防止传过来的顺序表为空 assert(ps); //判断空间是否充足 SLCheckCapacity(ps); //插入操作 //数据整体后移一位 for (int i = ps->size; i > 0;i--)//从后往前挪动，那么我们就将最后一位挪到下标为size的位置上 { ps->arr[i] = ps->arr[i - 1]; } //下标为0的位置空出来了 ps->arr[0] = x; ps->size++;//插入了数据，那么size就要增加 } //顺序表的打印操作 void SLPrint(SL* ps) { for (int i = 0; i < ps->size; i++) { printf("%d ", ps->arr[i]); } printf("\n"); } //尾部删除 void SLPopBack(SL* ps) { assert(ps); assert(ps->size);//这里的size不能为0，如果有效数据为0的话，那么就不能进行删除操作了 //ps->arr[ps->size - 1] = -1; /*上面这句话多余了 假设顺序表里面有1 2 3 4 现在我们要进行尾删除数据 我们进入代码直接指向了size--操作，那么现在的size就指向了4的位置 那么此时size就是3，有效的数据是3个 那么有效的数据是前三个数据1 2 3 假如我们要进行增加数据也是不会影响的 size--之后，我们在打印的时候都是以0到size-1这个范围进行操作的 变相的删除这个尾部的数据了 利用了size的变化 */ ps->size--;//有效数据减一 } /* 从前往后挪动 1 2 3 2先将1覆盖，然后3挪动到2之前的位置，那么我们就起到了头部删除 */ //头部删除 void SLPopFront(SL* ps) { assert(ps);//顺序表不能为空 assert(ps->size);//有效数据不能为空 //数据整体向前挪动一位 for (int i=0;i<ps->size-1; i++) { ps->arr[i] = ps->arr[i + 1];//将后面的数据覆盖到前面的数据 } ps->size--; } //在指定位置之前插入数据(空间足够才能直接插入) void SLInsert(SL* ps, SLDatatype x, int pos) { assert(ps); assert(pos>=0&&pos<=ps->size);//对pos的位置进行限制 //判断空间是否充足 SLCheckCapacity(ps); //将pos下标指向的数以及后面的数都往后挪动一位 for (int i=ps->size;i>pos; i--) { ps->arr[i] = ps->arr[i - 1];//前一个位置的值给到后面的位置，从后往前挪动 //最后一次就是将pos指向的位置上的数向后挪动到pos+1上面 //就是用pos上的数为pos+1位置上的数进行赋值 } //我们将pos位置上以及后面的数据往后挪了一步，那么现在的pos上就是空的 //我们现在为pos位置上进行数据的插入 ps->arr[pos] = x; ps->size++; } //删除指定位置的数据 void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0 && pos < ps->size);//不能等于，因为size指向的是最后一共额有效数据的下一个位置 //删除数据思路： /*我们将pos指向的数字删除了，那么pos指向的数字后面的数字都要往前挪动一位 size也要--操作 在挪动的时候我们是从前往后挪 */ //pos之后的数据整体向前挪动一位 for (int i=pos;i<ps->size-1 ;i++) { ps->arr[i] = ps->arr[i + 1]; //最后一次挪动的时候，我们要将size-1的值赋值到size-2上面 } ps->size--; } //查找数据 int SLFind(SL* ps, SLDatatype x) { assert(ps); for (int i=0 ; i < ps->size; i++) { if (ps->arr[i] == x) { return i; } } //说明没有找到：返回一个无效的下标 return -1; } #pragma once #include<stdio.h> #include<stdlib.h>//动态申请函数的头文件 #include<assert.h> //定义动态顺序表结构 typedef int SLDatatype; typedef struct SeqList { SLDatatype* arr;//定义一个指针 int capacity;//顺序表空间大小 int size;//记录顺序表中有效数据个数 }SL; //typedef struct SeqList SL;//为顺序表的类型名字进行重命名 //另一种重命名的方法就是在我们创建顺序表结构体的时候我们直接进行 //重命名，新名字直接写在下括号的后面，分号的前面 //顺序表的初始化 void SLInit(SL *ps); //销毁 void SLDestory(SL *ps); //打印顺序表 void SLPrint(SL* ps); //尾部插入数据 void SLPushBack(SL* ps, SLDatatype x);//往哪里插入数据，插入的数据是什么 //头部插入数据 void SLPushFront(SL* ps, SLDatatype x); //尾部删除 void SLPopBack(SL* ps); //头部删除 void SLPopFront(SL* ps); //在指定位置之前删除数据 void SLInsert(SL* ps, SLDatatype x, int pos); //删除指定位置的数据 void SLErase(SL* ps, int pos); //查找数据 int SLFind(SL* ps, SLDatatype x); //查找成功的话，返回顺序表对应下标的位置 顺序表算法题
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> /* 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。 假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作： 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。 返回 k。 用户评测： 评测机将使用以下代码测试您的解决方案： int[] nums = [...]; // 输入数组 int val = ...; // 要移除的值 int[] expectedNums = [...]; // 长度正确的预期答案。 // 它以不等于 val 的值排序。 int k = removeElement(nums, val); // 调用你的实现 assert k == expectedNums.length; sort(nums, 0, k); // 排序 nums 的前 k 个元素 for (int i = 0; i < actualLength; i++) { assert nums[i] == expectedNums[i]; } 如果所有的断言都通过，你的解决方案将会 通过。 示例 1： 输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2,_,_] 解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。 示例 2： 输入：nums = [0,1,2,2,3,0,4,2], val = 2 输出：5, nums = [0,1,4,0,3,_,_,_] 解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。 注意这五个元素可以任意顺序返回。 你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。 提示： 0 <= nums.length <= 100 0 <= nums[i] <= 50 0 <= val <= 100 */ //遍历数组，将数组中等于val的数据删除 //返回数组中与val不同元素的数量 /* 第一步：遍历数组，找val 一层循环 val之后的数据整体向前挪动一位 两层循环 那么时间复杂度就是O(N^2) */ /* 新思路：时间复杂度降到O(N) 空间复杂度是O(1),不需要额外的开辟空间+ 定义两个变量指向数组第一个位置，判断nuns[src]是否等于val 相等的话那么src++ 不相等的话，我们将src这个位置的数据给到nums[dst] ,然后src++和dst++ */ int removeElement(int* nums, int numsSize, int val) { int src = 0, dst = 0; while (src < numsSize) { if (nums[src] == val)//如果src指向的是我们要找的数字我们就将src++ { src++; } else//src指向的数字不是我们找的数字，我们就将src指向的数字赋值给dst指向的位置上的数字 { nums[dst] = nums[src]; dst++; src++; } } //此时det指向的位置就是要返回的有效个数 return dst; } /* 再次说明一下这个代码 假设我们的数组里面是2 2 3 4 6 我们要找到3，并返回非3的元素的个数 一开始我们的src和dst都指向的第一个元素 因为一开始src指向的数字不是我们要找的数字，那么我们 就进行src++ dst++操作 并将src指向的数字赋值给dst指向的位置上，因为都是指向的2，所以不变 然后src就指向了第二个元素的位置，dst也是指向了第二个元素的位置 因为src现在指向的数字还不是val，所以我们继续进行src++ dst++操作 并将src指向的数字赋值给dst指向的位置上，因为都是指向的2，所以不变 那么src指向了3，dst也是指向了3 因为此时的src找到我们要找的val，所以我们进行src++操作 那么src现在指向了4，dst仍然指向了3 那么因为现在的src指向的不是val，所以我们将src所指的数字赋值给dst指向的位置 那么现在dst位置上的就是4了 赋值完成之后src++和dst++ dst指向了第4个位置，src指向了第五个位置就是6 因为src指向的不是val，那么我们将src指向的6赋值给dst所指的位置 通过这种方法我们变相将val删除了，并且最后的dst的值就是非val有效个数 那么我们直接返回dst就行了 */ #define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> /* 给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过： 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。 返回 k 。 判题标准: 系统会用下面的代码来测试你的题解: int[] nums = [...]; // 输入数组 int[] expectedNums = [...]; // 长度正确的期望答案 int k = removeDuplicates(nums); // 调用 assert k == expectedNums.length; for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; } 如果所有断言都通过，那么您的题解将被 通过。 示例 1： 输入：nums = [1,1,2] 输出：2, nums = [1,2,_] 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。 示例 2： 输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4] 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。 提示： 1 <= nums.length <= 3 * 104 -104 <= nums[i] <= 104 nums 已按 非严格递增 排列 */ /*题目简介： * 删除数组中的重复元素，返回删除后数组的新长度 返回数组中唯一元素的个数 我们还要将数组进行改变 */ /*思路： * 定义两个指针，dst指向的第一个位置，sr指向的下个位置 * 判断src和dst位置的数字是否相等 * 相等的话就说明这两个数字重复了，那么src++，找到不相等的值 * 找到不相等的值我们就将dst++， * 然后我们将nums[src]赋值给dest位置上 * 赋值后src++ */ /*简单版本的思路： * （1）相等：src++ * （2）不相等：dst++,nums[dst]=nums[src],src++ */ /* 1 2 2 2 2 3 一开始我们的dst指向的是第一个元素，src指向的是第二个元素，因为两个元素不相等， dst++,指向了第二个元素，然后将src指向的数字赋值给dst指向的数字，因为指向的位置是一样的，那么数据就不变了 然后src++,src指向了第三个元素，判断是否相等，那么src++,那么src就指向了第三个元素 ，再次判断相等，相等，那么src++,src就指向了第四个元素 再次判断相等，相等，那么src++,src就指向了第五个元素 再次判断相等，相等，那么src++,src就指向了第6个元素3 不相等了，那么dst++，此时dst指向二档是第三个数据 那么我们将srx指向的3赋值给dst，然后src++，src就跳出数组了 那么此时dst的值是2，但是有效数据是3 所以我们在返回值的时候返回的是dst+1 */ int removeDuplicates(int* nums, int numsSize) { int dst = 0, src = 0; while (src < numsSize) { //判断nums[dst]和nums[src]数据是否相同 //相同就是重复了src++ //不相等：dst++, nums[dst] = nums[src], src++ //if (nums[dst] == nums[src]) //{ // src++; //} //else//不相同 //{ // dst++; // nums[dst] = nums[src]; // src++; //} //反正都是要src++的 if (nums[dst] != nums[src]&&++dst!=src) { //我们还在条件判断中写出了dst不等于src的条件我们就=不进行赋值了 /*dst++;我们直接在判断src和dst是否相等的时候进行后置++ 先++，再判断dst和src是否相等*/ //这种写法可以避免无效的赋值 nums[dst] = nums[src]; } src++; } return dst + 1; } #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> /* 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。 示例 1： 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] 解释：需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。 示例 2： 输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1] 解释：需要合并 [1] 和 [] 。 合并结果是 [1] 。 示例 3： 输入：nums1 = [0], m = 0, nums2 = [1], n = 1 输出：[1] 解释：需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。 提示： nums1.length == m + n nums2.length == n 0 <= m, n <= 200 1 <= m + n <= 200 -109 <= nums1[i], nums2[j] <= 109 进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？*/ //注意：一开始题目就说了nums1的大小是m+n //我们不需要额外申请空间，nums1里面的空间是足够的 /*场景一：l2先跳出循环 合并nums2到nums1中 nums1的初始长度是m+n,但是有效数据是m个 假设nums1: 1 2 6 _ _ _ nums2: 3 4 5 创建三个指针，第一个指针l1指向的是nums1的有效数据最后一个位置 第二个指针l2，指向的是nums2的有效数据最后一个位置 第三个指针l3，指向的是nums1的实际容量的最后一个位置 第一次比较l1指向的数字大于l2指向的数字，那么将l2的数字赋值到l3的位置 赋值过后，l1-- l3-- 注意l2不动，因为l2指向的数字还没有放到nums1里面 现在l2指向的是5，l1指向的是2，因为l2>l1所以将l2的5赋值到l3的位置 那么l2-- l3-- l2指向的是4 l1指向的是2，因为l2>l1,所以将l2的值赋值到l3的位置 赋值后l2-- l3-- 此时l2指向的是3，l3指向的是6 l1指向的是2 l1<l2 那么将l2指向的3赋值到l3指向的位置 l2-- l3-- 那么l1和l3就重合了 l2就跳出循环了 */ /*场景2 l1先跳出循环 nums1 3 4 5 _ _ _ nums2 1 2 6 l1指向了5 l2指向了6 l3指向的是nums1最后的位置 第一次l2>l1，那么将6赋值到l3的位置 放完后 l2-- l3-- l2指向的是2 l1指向的是5，l2<l1,所以将l1的值赋值到l3的位置， 那么l1-- l3-- l1指向的是4 ，l2指向的是2 因为 l1>l2，所以将l1指向的4赋值到l3的位置，那么l1-- l3-- 那么l1 指向的是3 l2指向的是2 l1>l2 所以将l1指向的3赋值到l3 的位置 l1-- l3-- 此时的l1已经跳出循环了 此时l2还有两个数据 那么我们就对这两个数据进行处理 l2指向的2赋值到l3的位置 l2-- l3-- 最后一个数字赋值到l3的位置 */ /*总结分析： 对于两种场景来说，结束条件要么是l1<0,要么是l2<0 对于l1<0，此时l2里面的数据还没有完全放到l1里面去，此时我们还要处理l2剩下的数据，循环放到l1中 对于l2<0的话，就说明l2里面的数据已经完全放到l1里面了，我们就不需要进行额外的处理了 */ /* 简易思路： 创建三个指针，分别指向nums1最后一个数据位置，nums2最后一个数据位置，nums1最后一个容量位置 比较l1和l2位置的数据，谁大谁往l3位置放数据 */ void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { int l1 = m - 1;//nums1中最后一个有效数据的下标 int l2 = n - 1;//nums2中最后一个有效数据的下标 int l3 = m + n - 1;//nums1中容量的最后位置的下标 //进行l1和l2数据的比较 while (l1>=0&&l2>=0) { if (nums1[l1] > nums2[l2]) { nums1[l3--] = nums1[l1--];//一定不能忘了l1--和l3-- } else { //l1==l2 要么l2>l1 nums1[l3--] = nums2[l2--];//将l2位置的数据放到l3位置处 } } //跳出while循环有两种情况，要么l1<0 要么l2<0 //不存在第三种情况吗？：l1<0 l2<0 同时跳出循环 while (l2 >= 0)//将l2剩下的数字循环放到l1中 { nums1[l3--] = nums2[l2--]; } } /* l1先<0的话需要处理 l2先<0的话不需要处理 */ 顺序表问题与思考
• 中间/头部的插⼊删除，时间复杂度为O(N) ,尾部的插入为O(1)
• 增容需要申请新空间，拷⻉数据，释放旧空间。会有不⼩的消耗。
• 增容⼀般是呈2倍的增⻓，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插⼊了5个数据，后⾯没有数据插⼊了，那么就浪费了95个数据空间。
思考：如何解决以上问题呢?
• 头部、中间位置的插入删除，时间复杂度变成O(1)
• 减少或者避免增容带来的性能消耗
• 避免空间浪费，要几个空间就给几个空间
那么接下来就是进行链表的学习了
3.单链表
• 头部、中间位置的插入删除，时间复杂度变成O(1)
• 减少或者避免增容带来的性能消耗
• 避免空间浪费，要几个空间就给几个空间
链表是否能解决这些问题呢？
链表也是一个统称，链表是线性表的一种
逻辑结构：线性
物理结构不一定是线性的
链表的结构与概念
概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
4.双向链表
与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/结点”
我们的理解就是链表是由一个个节点组成的
节点之间的地址不一定是连续的
节点有两个部分组成：数据+指向下一个节点的指针
单链表 ：SList single单身的
//节点的结构 typedef int LTDataType;//数据类型不一定是int类型 //方便我们后面一键替换 struct ListNode { LTDataType data; struct ListNode* next;//下个节点的指针，指向的类型是struct ListNode }; 在链表中没有增容的概念，直接插入新的数据，申请一个节点大小的空间就可以了，用malloc就行了
如果链表为空的话，pilist指向的是第一个结点，因为链表为空，那么plist指向的就是NULL
单链表的实现
#define _CRT_SECURE_NO_WARNINGS 1 #include"SList.h" void SLTPrint(SLTNode* phead) { SLTNode* pcur = phead;//pcur指向的是第一个节点的地址 while (pcur)//最后的时候pcur为NULL，我们就跳出了循环 { printf("%d->", pcur->data); pcur = pcur->next;//next指针保存的是下个节点的地址 } printf("NULL\n"); } //申请新节点 SLTNode* SLTBuyNode(SLTDataType x) { SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));//申请一个新节点 //一个节点的大小就是结构体的大小 if (node == NULL) { perror("malloc fail!"); exit(1); } node->data = x; node->next = NULL;//该节点指向的下一个指针是NULL return node; } void SLTPushBack(SLTNode** pphead, SLTDataType x) { //不能传空值 assert(pphead); //pphead---->&plist //对pphead进行解引用得到的就是plist SLTNode* newnode = SLTBuyNode(x); if (*pphead == NULL) { *pphead = newnode; } else { //尾节点-->新节点 //phead指向的是第一个节点，我们创建一个指针pcur,pcur指向的是phead //我们通过pcur来寻找尾节点 //找尾节点 SLTNode* pcur = *pphead; while (pcur->next != NULL) //最后一个节点的next是空指针，我们对于这个循环的 { pcur = pcur->next;//下一个节点的指针 } //pcur的下个节点我们不让他指向的是空指针，我们让他指向的是新的节点 pcur->next = newnode; } } //头部增加数据 void SLTPushFront(SLTNode** pphead, SLTDataType x) { assert(pphead); //申请一个新节点 SLTNode* newnode = SLTBuyNode(x); newnode->next = *pphead;//让新的节点的指针指向之前的头节点 *pphead = newnode;//原先是*pphead指向的头节点，现在头节点发生变化，我们让头节点变化为我们刚刚创建的新节点 } //尾部删除数据 void SLTPopBack(SLTNode** pphead) { //链表为空：不能进行删除 assert(pphead && *pphead);//pphead就是说传上来的数据不能为空，*pphead就是说明链表不能为空 //处理只有一个节点的情况：要删除的就是头节点,当前指针的next为NULL if ((*pphead)->next == NULL)//就说明只有一个节点 //因为箭头的优先级高，所以我们要将*pphead进行括起来 { free(*pphead);//我们直接将这个节点释放 *pphead = NULL; } else//不止一个节点 { SLTNode* ptail = *pphead;//头节点 *pphead就是plist SLTNode* prev = NULL;//前节点为空 //找尾节点 while (ptail->next != NULL) { prev = ptail;//prev指向ptail的前一个节点，在经历下面的代码之后 ptail = ptail->next; //我们让ptail指向下一个节点的之前，我们将现在的prev赋值为现在的ptail //等ptail指向下一个节点之后，那么prev就是一直指向的是前一个节点了 } //假设我们有4个节点，此时的prev指向的是第三个节点，ptail指向的是最后一个节点 //我们现在为了删除尾节点，我们将prev指向的下一个指针变为空指针 prev->next = NULL; free(ptail);//我们直接将ptail这个指针进行释放，因为这个指针指向的节点就是我们要删除的尾节点 ptail = NULL; } } //头部删除数据 void SLTPopFront(SLTNode** pphead) { assert(pphead && *pphead);//参数不能传空，链表不能为空 SLTNode* next = (*pphead)->next;//将下一个节点存储起来 free(*pphead);//直接将第一个节点进行释放 *pphead = next;//因为我们之前将下一个节点存储起来了 //现在我们将头节点删除了，那么新的头节点就是之前的下一个节点 //那么我们将头节点的地址赋值上之前存储的下一个节点的地址 //我们还能先改头结点，再进行释放 /* SLTNode*del=*pphead; *pphead=(*pphead)->next;//将头结点改变了 * free(del);//直接将头结点释放掉 dal=NULL; */ } //查抄 SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//返回的是一个节点的指针 { assert(phead); SLTNode* pcur = phead;//重新定义一个指针 while (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); if (pos == *pphead) { SLTPushFront(pphead, x); } else { //申请一个新的节点 SLTNode* newnode = SLTBuyNode(x); //找prev:pos的前一个节点 SLTNode* prev = *pphead;//初始定义为第一个节点 while (prev->next != pos)//prev的下个节点不是pos我们就一直进行循环 //直到我们的下个节点是pos,那么我们的prev就是pos的前一个节点了 //我们的目的就达到了 { prev = prev->next; } //此时已经是循环之外了，那么我们的prev已经是pos的前一个节点了 //我们在之前已经找到了prev和pos的位置，并且我们已经创建好了新的节点 //现在我们将新节点放到两个节点中间，就实现了指定位置插入了 newnode->next = pos; prev->next = newnode; } } //在指定位置之后插⼊数据 //我们就不用找pos前面的指针了， void SLTInsertAfter(SLTNode* pos, SLTDataType x) { assert(pos); //申请一个新的节点 SLTNode* newnode = SLTBuyNode(x); newnode->next = pos->next; pos->next = newnode; } //删除pos结点 pos前一个节点和后一个节点受到影响 void SLTErase(SLTNode** pphead, SLTNode* pos) { assert(pphead && *pphead); assert(pos); //头删特殊处理 if (pos == *pphead) { SLTPopFront(pphead); } else { SLTNode* prev = *pphead;//创建一个指针指向头结点 while (prev->next != pos) { prev = prev->next; } prev->next = pos->next;//pos前的节点指向pos的下一个节点 free(pos); pos = NULL; } } //删除pos之后的结点 void SLTEraseAfter(SLTNode* pos) { //我们需要知道三个节点，pos和pos后面要删除的节点以及删除节点后面的节点 assert(pos&&pos->next);//pos和pos的下个节点都不能为空 //pos pos->next pos->next->nxet SLTNode* del = pos->next;//将pos下个节点指针保存下来 //我们需要让pos后面结点指向的要删除的节点后面的节点 //我们要让pos节点后面是要删除的节点后面那个节点 pos->next = pos->next->next; free(del); del = NULL; } //销毁链表 void SListDestroy(SLTNode** pphead)//传址 { //遍历链表找到每个节点 //我们不能直接将第一个节点释放，我们要先将第二个节点进行保存 //如果提前将第一个节点删除了我们就找不到后面的节点了 assert(pphead && *pphead);//不能传空，不能传空链表 //创建一个指针遍历链表 SLTNode* pcur = *pphead;//先指向第一个节点 while (pcur != NULL) { SLTNode* next = pcur->next;//将pcur指向的下个节点进行保存 free(pcur); pcur = next; } //跳出循环的时候,pcur已经指向的是NULL *pphead = NULL; } #pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> //定义链表（结点）的结构 typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }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* phead, SLTDataType x);//返回的是一个节点的指针 //在指定位置之前插⼊数据（传二级指针，就说明我们要将链表中数据进行改变）(时间复杂度是O(N)) void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x); //在指定位置之后插⼊数据(时间复杂度是O(1)) void SLTInsertAfter(SLTNode* pos, SLTDataType x); //删除pos结点 void SLTErase(SLTNode** pphead, SLTNode* pos); //删除pos之后的结点 void SLTEraseAfter(SLTNode* pos); //销毁链表 void SListDestroy(SLTNode** pphead); #define _CRT_SECURE_NO_WARNINGS 1 #include"SList.h" //创建一个链表，并打印链表 void creatSList() { //链表是由一个个节点组成的 SLTNode*是结构体指针 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; /* 我们申请了四个节点，每个节点里面都有一个date和下一个节点的指针 */ node1->next = node2; node2->next = node3; node3->next = node4; node4->next = NULL;//最后一节点的指针指向的是NULL //打印链表 //将第一个节点的地址作为参数传递过去 SLTPrint(node1); } void SListTest01() { SLTNode* plist = NULL; //SLTPushBack(&plist, 1);//因为phead是一级指针，所以我们在接受的时候我们要用二级指针进行接收 //SLTPrint(plist); //SLTPushBack(&plist, 2); //SLTPushBack(&plist, 3); //SLTPrint(plist); //为什么打印出来的都是NULL //phead发生改变，但是plist没有发生改变，形参改变，但是实参没有改变，那么我们应该进行传址操作 /* 第一个节点：*plist 指向第一个节点的指针：plist 指向第一个节点的指针的地址：&plist----->pphead*/ SLTPushFront(&plist, 1); SLTPushFront(&plist, 2); SLTPushFront(&plist, 3); SLTPushFront(&plist, 4); SLTPrint(plist);//期望结果：4->3->2->1->NULL //尾删 /*SLTPopBack(&plist); SLTPrint(plist);*/ /*打印出来的结果就是 4->3->2->1->NULL 4->3->2->NULL */ /*SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist); SLTPopBack(&plist); SLTPrint(plist);*/ /* 当链表还只剩下一个节点的时候我们要进行处理了，因为剩一个节点的时候我们没有前置节点了 */ //进行处理之后我们得到的结果就是这样的 /* 4->3->2->1->NULL 4->3->2->NULL 4->3->NULL 4->NULL NULL */ //如果我们进行第五次的删除的操作的话，就会报错了Assertion failed: pphead && *pphead, file /*SLTPopFront(&plist); SLTPrint(plist);*/ //查找节点 SLTNode* find=SLTFind(plist,2 ); /*if (find == NULL) { printf("没有找到\n"); } else {` printf("找到了\n"); }*/ //SLTInsert(&plist, find, 11);//在3之前插入11 期望结果就是4->11->3->2->1->NULL //SLTPrint(plist); /*我们将要查找的数字改为4，我们在4之前插入数据，但是出现了报错 * 那为什么会报错呢？ 因为此时的pos是头节点，前面是没有节点的 ，但是我们一开始是将prev定义为第一个节点的， 我们一直满足循环的条件，一直进行循环，那么代码中的while就成了一个死循环 所以我们要对着这种情况进行特殊处理的 我们直接调用头插函数 */ /*SLTInsertAfter(find, 11); SLTPrint(plist);*/ //SLTErase(&plist, find); //SLTPrint(plist);//尾删没问题，但是头删有问题 //对于头删，pos是头节点，那么一开始的prev指向的是头结点，一直满足循环 //就一直循环下去了 //所以我们要进行特殊处理下 /*SLTEraseAfter(find); SLTPrint(plist);*/ SListDestroy(&plist); SLTPrint(plist); } int main() { SListTest01(); //creatSList(); return 0; } 链表头插的时间复杂度是O(1)
链表头删的时间复杂度是O(1)
链表的分类
虽然有这么多的链表的结构，但是我们实际中最常⽤还是两种结构：单链表和双向带头循环链表
⽆头单向⾮循环链表：结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦结构，如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。
带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带来很多优势，实现反⽽简单了，后⾯我们代码实现了就知道了。
双向链表我们能从头遍历到尾，我们也能从尾遍历到头
在带头链表中，除了头结点，其他节点都存储有效的数据
头节点的作用是占位子的，叫做“哨兵位”
不带头的链表，从第一个节点开始就是存储的就是有效的数据
带环链表尾节点next不为空
那么单链表的全称是：不带头单向不循环链表
双向链表：带头双向循环链表
双向链表结构相较于单链表来说结构要复杂一些，但是接口的实现要比单链表简单很多
4.双向链表
双向链表：带头双向循环链表
双向链表结构相较于单链表来说结构要复杂一些，但是接口的实现要比单链表简单很多
双向链表的节点结构：数据+指向后一个节点的指针+指向前一个节点的指针
尾节点的next指针指向哨兵节点
struct ListNode { int data; struct ListNode* next;//下个节点的指针 struct ListNode* prev;//指向前个节点的指针 }; 双向链表为空的情况：只有一个自循环的哨兵位
第一个节点：第一个有效的节点
哨兵位：头节点
新插入的数据的尾节点要指向哨兵位，prev指针要指向前一个节点
我们还要改变新节点之前的节点的next指针的指向，要指向新的节点
我们的哨兵位的prev指针还要指向新的尾节点
那么我们在插入新节点的时候，受到影响的节点有之前的尾节点和哨兵位以及新节点
在存在新的节点的情况下，我们的哨兵位的perv指针指向的是尾节点
#define _CRT_SECURE_NO_WARNINGS 1 #include "List.h" LTNode* LTBuyNode(LTDataType x)//创建节点 { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail!"); exit(1);//直接退出 } newnode->data = x; newnode->next = newnode->prev = newnode;//让这两个指针都指向当前节点的自己，实现循环的效果 return newnode; } 初始化 //void LTInit(LTNode** pphead) //{ // //创建一个头结点（哨兵位） // *pphead = LTBuyNode(-1); //} LTNode* LTInit1()//通过返回值的方法进行初始化，我们要返回一个哨兵位节点的指针 { LTNode* phead = LTBuyNode(-1);//创建一个指向哨兵位节点的指针 return phead; } //销毁 链表的销毁是整个都销毁的 void LTDesTory(LTNode** pphead) { //我们需要遍历这个链表，一个个删除 assert(pphead && *pphead);//哨兵位不能为空，参数也不能传一个空链表 LTNode* pcur = (*pphead)->next;//创建一个指针让这个指针指向哨兵位的下个节点,就是第一个有效非节点 //我们从哨兵位的下个节点进行销毁操作 while (pcur != (*pphead))//循环操作一直进行到下个节点不是哨兵位 { LTNode* Next = pcur->next;//创建一个指针指向pcur的下个节点，进行保存 free(pcur); pcur = Next;//让pcur这个指针走到Next指向的节点 } //遇到哨兵位跳出循环了 //销毁哨兵位节点 free(*pphead); *pphead = NULL; pcur = NULL; } //打印链表 void LTPrint(LTNode* phead) { LTNode* pcur = phead->next;//定义一个指针指向哨兵位的next指向的第一个有效的节点 //那么我们就从第一个有效的节点开始打印了 while (pcur != phead)//直到pcur走到哨兵位的位置我们就跳出循环了 { printf("%d ->", pcur->data);//打印当前节点保存的数据 pcur = pcur->next;//在链表中进行遍历 } printf("\n"); } //尾插数据 void LTPushBack(LTNode* phead, LTDataType x) { //断言一下，传的参数一定要是有效的参数 assert(phead); LTNode* newnode = LTBuyNode(x);//创建新的节点 //phead(哨兵位) phead->prev(之前的尾节点) newnode(新插入的节点) //我们先进行newnode的指针修改，prev指向上个尾节点，next指向哨兵位 newnode->next = phead; newnode->prev = phead->prev;//之前的尾节点的表示就是phead->prev //我们再对原先的尾节点进行指针的修改，原先的next指针指向的是哨兵为，那么现在就指向的是新节点了 phead->prev->next = newnode; //接下来我们对哨兵位进行修改 //哨兵位的prev原本指向的是之前的尾节点，那么我们现在让Prev指新节点 phead->prev = newnode; //与单链表相比的话，我们不用判断链表是不是空的，我们也不用从头开始遍历来找尾节点 } //头插数据 哨兵位之后 头插到第一个有效数据的前面 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); //创建新节点 LTNode* newnode = LTBuyNode(x); //我们先修改插入数据的指针指向，因为newnode的指针指向不会影响原链表 newnode->next = phead->next;//指向原先的第一个节点 newnode->prev = phead;//prev指向哨兵位 //我们头插的节点的next指向的是之前的第一个有效的节点 //prev指向的是哨兵位 //我们还要改变之前的第一个有效节点的Prev指针的指向，让指针指向位头插的新数据 phead->next->prev=newnode;//原先的第一个有效节点的prev指针指向新插入的数据 //还有就是哨兵位的next指针要指向新插入的节点了 phead->next = newnode; } //判断链表是否为空 bool LTEmpty(LTNode* phead) { assert(phead); return phead->next == phead;//如果哨兵位的next指针指向的是自己，那么就说明这个链表是空链表 }//如果链表为空的话，那么就返回的是true //尾删数据 void LTPopBack(LTNode* phead) { assert(phead);//哨兵位不能为空 assert(!LTEmpty(phead));//判断链表不为空，那么我们就能进行删除节点的操作了 //我们删除节点的话，我们是将哨兵位prev指向的尾节点删掉 //我们将尾节点删掉的话，收到影响的节点有哨兵位和尾删节点的前一个节点 /* 如果将尾节点删掉的话，我们的删掉节点前一个节点的next指针需要指向head' 并且head的prev指针要指向我们的删除节点的前一个节点 我们要创建一个指针指向删除的节点，以便寻找到删除节点的前一个节点 那么我们通过哨兵位就能找到要删除的节点以及他之前的节点 */ //del是要删除的节点 //del(phead->prev) prev(del->prev) phead LTNode* del = phead->prev;//创建一个指针指向我们要删除的节点 LTNode* prev = del->prev;//删除节点的前一个节点 //我们先修改prev节点的指针 prev->next = phead;//prev指向了哨兵位 phead->prev = prev;//哨兵位的prev指向了prev，那么现在prev指向的节点就是新的尾节点了 //因为我们之前创建了指针指向我们要删除的节点，那么我们通过这个指针将节点删除 free(del); del = NULL; } //头删数据 删除第一个有效节点 void LTPopFront(LTNode* phead) { assert(phead);//哨兵位不能为空 assert(!LTEmpty(phead));//判断链表不为空，那么我们就能进行删除节点的操作了 /*删除第一个节点受到影响的节点有哨兵位以及第二个有效节点 删除第一个节点之后我们哨兵位的next指针要指向第二个节点 第二个节点的prev指针要指向我们的哨兵位*/ LTNode* del = phead->next;//创建一个指针指向我们要删除的节点,就是现在的第一个节点 //我们先改第二个指针的prev指针的指向 del->next->prev = phead;//第二个节点的prev指针要指向哨兵位 phead->next = del->next;//哨兵位的下个节点是第二个节点 free(del); del = NULL; } //查找数据 LTNode* LTFind(LTNode* phead, LTDataType x)//返回值是指向节点的指针 { //我们需要进行链表的遍历，我们找一圈就行了，再次遇到哨兵位我们直接跳出循环 LTNode* pcur = phead->next;//我们从第一个有效的节点进行遍历 while (pcur != phead)//如果下个节点是哨兵位我们直接跳出循环 { if (pcur->data == x) { return pcur;//找到了我们直接返回这个节点的地址 } pcur = pcur->next;//没有找到我们继续往后找 } return NULL;//找不到了，直接返回空 } //在pos位置之后插入节点 void LTInsert(LTNode* pos, LTDataType x) { /* 我们先将要插入的节点的next和prev指针进行解决 我们先将newnode 的next和prev处理好 我们是在pos这个位置的后面进行插入节点，那么就会影响到pos和pos->next这两个节点 我们要将pos的next指针进行改变，指向了新的节点以及pos原先后面的节点的prev指向的位置要变为新的节点 */ //创建一个节点 LTNode* newnode = LTBuyNode(x); //pos newnode pos->next //先处理newnode newnode->next = pos->next; newnode->prev = pos; //处理pos后面节点的prev指针的指向 pos->next->prev = newnode; //改变pos的next指针的指向 pos->next = newnode; } //删除指定位置的节点 void LTIErase(LTNode* pos) { assert(pos);//传过来的位置不为空 /*删除指定位置的节点 pos前面的节点pos->prev pos后面的节点pos->next 那么删除pos就出影响到这两个节点了 pos前面指针的节点的next指针就会指向了Pos后面的节点了 pos后面的节点的prev指针就会指向了pos前面的节点了*/ pos->prev->next = pos->next; pos->next->prev = pos->prev; free(pos); pos = NULL; } void LTDesTory2(LTNode* phead) { assert(phead); LTNode* pcur = phead->next;//定义一个指针指向哨兵位的下个节点，就是第一个有效节点 while(pcur != phead)//遇到哨兵位就跳出 { LTNode* Next = pcur->next;//创建一个指针指向当前位置的下个节点 free(pcur); pcur = Next; } free(phead); phead = NULL; pcur = NULL; //我们已经将链表的空间销毁了，但是plist仍然指向原先的那片空间 //所以我们需要进行手动将plist置为NULL } #pragma once #include<stdlib.h> #include<stdio.h> #include<assert.h> #include<stdbool.h> //定义双向链表节点的结构 typedef int LTDataType;//链表数据类型 typedef struct ListNode { LTDataType data; struct ListNode* next; struct ListNode* prev; }LTNode; //为了保持接口的一致性，优化接口都为一级指针 //初始化 //void LTInit(LTNode**pphead);//我们拿着一个空瓶子让老板给我们装饮料 LTNode* LTInit1();//直接让老板给我们一个装好了的饮料 //通过返回值的方法初始化 //销毁 链表的销毁是整个都销毁的 void LTDesTory(LTNode** pphead); void LTDesTory2(LTNode* phead);//传一级我们需要手动将plist置为NULL //打印链表 void LTPrint(LTNode* phead); //尾插数据 //第一个参数传一级还是二级，，要看pphead指向的节点会不会发生改变 //如果发生改变，那么pphead的改变要影响实参，传二级 //如果不发生改变，pphead不会影响实参，传一级 //我们通过传递的一级指针来找到头结点，就可以找到之后的节点了 //那么我们在插入新节点的时候，受到影响的节点有之前的尾节点和哨兵位以及新节点 void LTPushBack(LTNode* phead, LTDataType x); //头插数据 void LTPushFront(LTNode* phead, LTDataType x); //尾删数据 void LTPopBack(LTNode* phead); //头删数据 void LTPopFront(LTNode* phead); //判断链表是否为空 bool LTEmpty(LTNode* phead); //查找数据 LTNode* LTFind(LTNode* phead, LTDataType x); //在pos位置之后插入节点 void LTInsert(LTNode* pos, LTDataType x); //删除指定位置的节点 void LTIErase(LTNode* pos); #define _CRT_SECURE_NO_WARNINGS 1 #include "List.h" void ListTest01() { //创建双向链表变量 /*LTNode* plist = NULL; LTInit(&plist);*///这个里面的哨兵位是自循环的 //初始化操作优化 LTNode* plist = LTInit1();//调用这个函数直接给我们一个指向哨兵位的指针 //这种初始化操作之后我们就不用在外面创建指针传过去了 //尾插 LTPushBack(plist,1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPrint(plist); //头插 /*LTPushFront(plist, 1); LTPrint(plist); LTPushFront(plist, 2); LTPrint(plist); LTPushFront(plist, 3); LTPrint(plist); LTPushFront(plist, 4); LTPrint(plist);*/ //尾删 /*LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist);*/ //头删 /*LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPrint(plist);*/ //查找数据 LTNode*pos=LTFind(plist, 1); /*if (pos == NULL) { printf("没有找到\n"); } else { printf("找到了\n"); }*/ //删除指定位置之后的节点 /*LTInsert(pos, 11); LTPrint(plist);*/ //删除pos位置上的节点 LTIErase(pos); LTPrint(plist); //销毁操作 LTDesTory(&plist); } int main() { ListTest01(); return 0; 不难发现我们的双向链表在操作的时候基本上都是传的一级指针
5.顺序表与链表的分析
那么顺序表和链表哪个好呢？
我们在对顺序表插入数据时，我们要将插入位置后面的节点都往后移动
但是对于链表的话，我们直接修改指针的指向就行了，不需要对节点做任何的操作
我们在使用顺序表的时候增容的时候存在空间浪费
但是顺序表就不会，要多少就给多少，不存在空间浪费
根据不同的场景选择对应数据结构
6.单链表OJ题
题目一：移除链表元素
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> #include <stdlib.h> //Definition for singly-linked list. struct ListNode { int val; struct ListNode *next; }; /* 将链表中是val的节点删除 */ /* 思路一：遍历链表，在原链表执行删除指定节点的操作 思路二：不修改原链表 创建新链表，将原链表中值不为val的节点尾插到新链表中 */ typedef struct ListNode ListNode;//结构体名称叫ListNode struct ListNode* removeElements(struct ListNode* head, int val)//返回的是一个节点的指针 { //创建新链表 ListNode* newHead, * newTail;//创建两个链表指针 newHead = newTail = NULL; //newTail是尾节点指针，newHead是头节点指针 //遍历原链表 ListNode* pcur = head;//head就是题目给出的原链表的头节点 while (pcur != NULL) { //找值不为val的节点，往新链表中进行尾插操作 if (pcur->val != val) { //尾插 //链表为空（头结点为空） if (newHead == NULL) { newHead = newTail = pcur;//此时既是头节点也是尾节点 } //链表不为空（头结点不为空） else { newTail->next = pcur;//假设我们现在有一个节点，我们插入一个新的节点，那么现在我们要将即将插入的pcur插入到newTail->nex这个位置，因为此时的newTail还在头节点上，进行完操作之后，pcur变成了新的尾节点，那么我们将为节点赋值到pcur在的位置 上面的代码就是将pcur放到newTail->next这个位置 //然后newTail就更新位置了 newTail = newTail->next;//让newTail走到下个节点 } } //尾插结束后,pcur继续往后走 pcur = pcur->next; } //跳出循环了，我们已经将不是val的值都拿到新的链表中进行尾插了 //那么此时我们就依照题目返回新的头节点 //让新链表的尾节点指向空 //假设给我们的节点是7->7->7 //我们要将7删除，那么新链表就为空，下面就是处理这种情况的 if (newTail)//新链表不为空 { newTail->next = NULL; } return newHead; } void test01() { //创建一个测试的链表，4个节点 //1->6->1->6 ListNode* n1 = (ListNode*)malloc(sizeof(ListNode)); n1->val = 1; ListNode* n2 = (ListNode*)malloc(sizeof(ListNode)); n2->val = 6; ListNode* n3 = (ListNode*)malloc(sizeof(ListNode)); n3->val = 1; ListNode* n4 = (ListNode*)malloc(sizeof(ListNode)); n4->val = 6; n1->next = n2; n2->next = n3; n3->next = n4; n4->next = NULL; //1->6->1->6 ListNode* plist = n1; //构造一个链表 removeElements(plist, 6);//将数字为6的节点删掉 //预期结果1->1 } int main() { test01(); return 0; } /* 对于经过删除val操作的新链表，这个的节点是1->1->6 可见第二个1的节点的next并没有改变 假设我们给的链表是1 2 6 3 4 5 6 在将5放到新链表后，没有进行一个好的处理，此时的5的next指针还是指向的是6 我们要让新链表的尾指针指向空 */ 题目二：反转链表
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ /*思路一：将第一个链表头插到一个新链表 思路二：创建三个指针，分别为n1 n2 n3 通过这三个指针我们能在原链表的基础上修改指针的指向（不需要创建新的链表） */ /* 解释下思路二： 一开始我们的n1是空指针，n2指向的是1，n3指向的是2 我们将n2的指向改变指向n1，然后1就指向了空指针1->NULL 然后我们将n1放到n2的位置,n2放到n3的位置，那么现在n1指向的是1,n2指向的是2，n3指向的是3 我们将n2的指向改变指向为n1 2->1->NULL 然后我们将n1放到n2的位置,n2放到n3的位置，那么现在n1指向的是2,n2指向的是3，n3指向的是4 我们将n2的指向改变指向为n1 3->2->1->NULL 然后我们将n1放到n2的位置,n2放到n3的位置，那么现在n1指向的是3,n2指向的是4，n3指向的是5 我们将n2的指向改变指向为n1 4->3->2->1->NULL 然后我们将n1放到n2的位置,n2放到n3的位置，那么现在n1指向的是4,n2指向的是5，n3指向的是走出去了 我们将n2的指向改变指向为n1 5->4->3->2->1->NULL 最后n1走到n2,n2走到n3 n2和n3都走出去了，现在的n1指向的是5的位置，那么现在的5就是新的头结点了 那么此时的n1就是链表新的头结点了 总结下我们将n2指向n1，然后将n1放到n2的位置，n2放到n3的位置 */ typedef struct ListNode ListNode; struct ListNode* reverseList(struct ListNode* head)//返回值是一个指向节点的指针 { //处理下空链表情况 if(head==NULL) { return head; } //创建三个指针 ListNode*n1,*n2,*n3; n1=NULL; n2=head; n3=n2->next; while(n2!=NULL)//n2不为空，那么循环就一直进行 { n2->next=n1; n1=n2; n2=n3; if(n3)//判断n3是否为空 n3=n3->next;//注意n3会哦提前走到为空 { n3=n3->next;//n3不为空我们就让n3往下走 } } //除了循环，那么此时的n2就是NULL //那么此时的n1就是链表反转后新的头节点 return n1; } 题目三：链表的中间节点
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ //给你单链表的头结点 head ，请你找出并返回链表的中间结点。 //如果有两个中间结点，则返回第二个中间结点。 /*思路一： 第一次循环：求链表总长度，计算中间节点的位置 第二次循环：从头结点走到中间节点 思路二：快慢指针 slow和fast指针 慢指针每次走一步，快指针每次走两步 当链表节点为奇数的情况下： 我们直到fast的条件满足fast->NULL,fast的下个节点是空指针我们就停下来，此时的slow指针就是中间值的位置 当链表节点为偶数的情况下： fast走向了空那么此时的slow也恰好是我们所规定的中间节点 那么总结下：奇数节点下，当fast的下一个节点是空指针的话，那么此时的slow就是中间指针 偶数节点下，fast恰好走到空指针，那么那么此时的slow就是中间指针 */ typedef struct ListNode ListNode; struct ListNode* middleNode(struct ListNode* head) { ListNode*slow=head,*fast=head; //慢指针每次走一步 //快指针每次走两步 while(fast&&fast->next)//两个条件不能为空 //对于这个循环的顺序我们有要求吗？ //能不能让这两个循环条件换位置呢？ /* 对于这种情况：fast->next&&fast 当我们是奇数个节点的话，此时的fast下个节点是空的，那么我们就不能进入循环了，我们直接跳出循环了，此时的结果就是我们要的 当我们是偶数个节点的时候，fast->next&&fast。那么此时的fast恰好是空指针，我们是不能用空指针来找下个节点的，那么这个代码就会报错了 fast&&fast->next这个条件这么写两种情况都能照顾上了 */ //对于这个循环条件我们不能用或， //假设我们这里是或的话，我们fast下个节点是空节点，我们就满足循环条件了 //再次进入循环了，那么我们的fast和slow两个指针又开始移动起来了 { slow=slow->next; fast=fast->next->next; } //跳出循环 //此时的slow指向的节点刚好就是中间节点 return slow; } 为什么快慢指针能找到中间节点呢？
慢指针每次走一步，快指针每次走两步，当快指针走到链表的尾节点时
假设链表的长度为n,快指针走的路程是慢指针走的两倍，此时的慢指针走的路程就是n/2
注意：在while内循环的条件只能是：fast&&fast->next
题目四：合成两个有序列表
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ /* 思路： 创建一个新的链表，令l1指向链表1，l2指向链表2 如果l1<l2的话，那么就将l1先放到新链表里面 一次进行l1和l2的比较 如果哪个链表里面的数据优先迁移完成，那么我们就将剩下的节点放到新链表内 思路总结： 先创建新链表， 遍历两个链表，依次比较大小，谁小我们就尾插到新链表中 */ /* 假如我们在进行链表的尾插的时候，假设我们是往空链表里面进行插入操作的话 我们插入的节点既是尾节点，也是头节点， 假如我们在进行插入的时候，前面已经有了节点，那么我们需要插入到上一个尾节点的下一个节点，并且此次插入的节点成为新的尾节点 */ /*假如传的两个链表都是空的，那么我们返回的就是空链表就行了*/ typedef struct ListNode ListNode; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)//返回的是节点的指针,参数是两个链表的头结点 { //处理链表为空的情况 if(list1==NULL&&list2==NULL) { return NULL; } if(list1==NULL) { return list2; } if(list2==NULL) { return list1; } //创建新的空链表 ListNode*newHead=NULL,*newTail=NULL; //创建两个指针分别指向两个链表的头节点 list1和list2都是两个链表的头节点 ListNode*l1=list1; ListNode*l2=list2; //进行比大小 while(l1&&l2)//只要一个为空走完了我们就跳出循环 { if(l1->val<l2->val) //l1里面节点的值小于l2z节点的值，我们先放l1 { //存在两种情况，链表是否为空的 if(newHead==NULL) { newHead=newTail=l1; } else { //说明链表不为空 newTail->next=l1;//我们往这个位置插入 newTail=newTail->next;//那么这个节点就是新的尾节点了 } //将l1尾插到新链表中 l1=l1->next;//让l1继续往后走 } else { //将l2尾插到新链表中 //存在两种情况，链表是否为空的 if(newHead==NULL) { newHead=newTail=l2; } else { //说明链表不为空 newTail->next=l2;//我们往这个位置插入 newTail=newTail->next;//那么这个节点就是新的尾节点了 } l2=l2->next;//让l2继续往后走 } } //跳出循环只有两种情况：要么l1为空（l2肯定不为空），要么l2为空（l1肯定不为空） if(l1)//l1不为空的话，我们将l1剩下的都插入到新链表中 { newTail->next=l1; } if(l2)//l1不为空的话，我们将l2剩下的都插入到新链表中 { newTail->next=l2; } return newHead; } /*思考：为什么最后的不是while循环呢？而是if语句呢？ 这个就涉及到了链表的神奇之处 假设我们最后的l1已经全部放到新链表内， 但是l2还有剩下的，并且不止一个有3个，是3 4 5 我们将3放到新链表中，那么剩下两个节点我们 就不许要进行操作了 因为我们并没有改变3的下个节点，3的下个节点还是4，所以我们仅仅只需要将剩下没放到新链表的数据中的一个数据放到新链表中，剩下的节点一直都在链接着的 */ typedef struct ListNode ListNode; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)//返回的是节点的指针,参数是两个链表的头结点 { //处理链表为空的情况 if(list1==NULL&&list2==NULL) { return NULL; } if(list1==NULL) { return list2; } if(list2==NULL) { return list1; } //创建新的空链表 //ListNode*newHead=NULL,*newTail=NULL; //现在我们不想创建一个空链表，我们创建一个非空链表 ListNode*newHead,*newTail; newHead=newTail=(ListNode*)malloc(sizeof(ListNode)); //此时我们创建的newHead就不是空的了，newHead就指向了一块有效的空间 //创建两个指针分别指向两个链表的头节点 list1和list2都是两个链表的头节点 ListNode*l1=list1; ListNode*l2=list2; //进行比大小 while(l1&&l2)//只要一个为空走完了我们就跳出循环 { if(l1->val<l2->val) //l1里面节点的值小于l2z节点的值，我们先放l1 { newTail->next=l1;//我们往这个位置插入 newTail=newTail->next;//那么这个节点就是新的尾节点了 l1=l1->next;//让l1继续往后走 } else { //将l2尾插到新链表中 newTail->next=l2;//我们往这个位置插入 newTail=newTail->next;//那么这个节点就是新的尾节点了 l2=l2->next;//让l2继续往后走 } } //跳出循环只有两种情况：要么l1为空（l2肯定不为空），要么l2为空（l1肯定不为空） if(l1)//l1不为空的话，我们将l1剩下的都插入到新链表中 { newTail->next=l1; } if(l2)//l1不为空的话，我们将l2剩下的都插入到新链表中 { newTail->next=l2; } //因为我们一开始创建的链表就不是空的，并且一开始的newHead就指向了我们创建的新节点 //那么进行更改之后我，我们应该返回的是newHead->next ListNode*ret=newHead->next; free(newHead); newHead=NULL; return ret; } //因为我们的一开始是用malloc申请空间的，那么代码结束就应该释放掉 //但是如果直接释放的话我们是找不到我们合并后的链表的， //所以在释放链表之前我们应该要将newHead->next这个节点进行保存 在优化版本中，我们因为创建的是一个非空的链表，所以存在一个我们创建的节点，那么一开始的头结点和尾节点都是这个节点，我们再在这个节点后面进行插入节点
这个节点就是用来占位子的，没有保存任何有效的数据
对于这种方法我们就不用判断是否为空链表
题目五：链表分割
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ //在c++中我们不需要重新定义名字，我们直接用ListNode /* 思路：我么还能创建一个大链表，一个小链表 将遍历原先的链表，将比x小的节点放到小链表里面 将比x大的节点放到大链表里面 然后我们再进行大小链表的对接 3我们将小链表的尾链表的下一个节点变成大链表头结点的下一个节点 因为我们在创建的大小链表的时候，用的是malloc开辟的节点，因此大小链表的头结点就相当一个站位置的 并不是一个有效的节点 */ class Partition { public: ListNode* partition(ListNode* pHead, int x)//返回链表的头节点 { //创建两个非空链表 ListNode*lessHead,*lessTail; //小链表 lessHead=lessTail=(ListNode*)malloc(sizeof(ListNode));//开辟一个节点大小的空间 //大链表 ListNode*greaterHead,*greaterTail; greaterHead=greaterTail=(ListNode*)malloc(sizeof(ListNode)); //创建一个临时指针遍历链表，找小于x的和其他节点位插到大小链表中 ListNode*pcur=pHead;//初始化指向头节点 while(pcur)//等价与pcur!=NULL { if(pcur->val<x)//尾插到小链表 { //因为我们的大小链表都是非空的，那么我们直接往头节点后面进行尾插 lessTail->next=pcur; lessTail=lessTail->next;//尾节点走到新的位置 } else //尾插到大链表 { greaterTail->next=pcur; greaterTail=greaterTail->next; } pcur=pcur->next;//pcur换下个节点进行比较 } //跳出循环，说明此时我们的原链表已经遍历完了 //我们现在要让大链表和小链表进行首尾相连 lessTail->next=greaterHead->next; greaterTail->next=NULL; //此时我们要将lessHead和greatHead进行释放 //但是我们题目要求是将新的链表的头结点进行返回， //但是如果我们先将lessHead进行释放的话，那么我们是无法找到头节点的 //所以我们在释放操作之前我们需要将头结点进行比保存 //定义一个指针指向小节点第一个有效的节点 ListNode*ret=lessHead->next; free(lessHead); lessHead=NULL; free(greaterHead); greaterHead=NULL; //返回头节点 return ret; } };/* 对于这个题来说的话 假设我们原先的链表是5->1->3->6->2 经过一系列操作后我们得到了大小两个链表 小链表：头结点->1->2 大链表：头节点—>5-3->6 再次进行操作得到了 1->2—>5-3->6 但是我们有没有想过这个题目会出现死循环呢？ 因为在之前我们没有对6的下个节点进行操作，如果不进行操作的话 那么这个链表的指向就是这样的：1->2—>5-3->6->2—>5-3->6->2—>5-3->6 ....... 所以我们需要将6的下个节点指向NULL */ 题目六：链表的回文结构
回文结构就是轴对称结构
思路一
/* 思路一：创建新的数组，遍历原链表，将链表节点中的值放入数组中，在数组中判断是否为回文结构 */ class PalindromeList { public: bool chkPalindrome(ListNode* A) { int arr[900]={0}; ListNode *pcur=A; int i=0; while(pcur)//遍历原链表，pcur不能为空 { //将链表中每个节点的值放到arr中 arr[i]=pcur->val; i++; pcur=pcur->next;//换下一个节点 } //i即节点的个数，因为我们的i一直在进行++操作 //找中间节点，判断是否为回文数字 int left=0; int right=i-1;//i是数组中数据的有效个数 //我们比较left和right的下标的数字的大小，相等的话我们就让两个指针一直走，直到遍历整个数组 while(left<right) { if(arr[left]!=arr[right]) { //那么肯定不是回文结构 return false; } right--; left++; } //说明是回文结构，因为已经跳出循环了 return true; } }; //这道题我们注意：我们开辟了空间，arr[900] //但是假如我们碰到的题没有对链表节点个数进行限制的话，那么这种思路的话肯定是不行的 //除此之外，该思路只能在牛客上通过，力扣是不行的 创建两个指针，left和right
分别从左到右和从右到左进行遍历
我们判断对应下标的数据是否相等
如果出现了不相等的情况，那么这个链表就不具有回文结构了
思路二
class PalindromeList { public: ListNode*findMidNode(ListNode* phead)//封装一个函数来找中间节点 { //快慢指针 ListNode*slow=phead; ListNode*fast=phead; while(fast&&fast->next)//fast和fast下个节点不为空 { slow=slow->next;//慢指针每次走一步 fast=fast->next->next;//快指针每次走两次 } //那么此时的slow节点刚好指向了中间节点 return slow; } ListNode*reverseList(ListNode* phead)//封装一个函数来反转链表 { ListNode*n1,*n2,*n3; n1=NULL; n2=phead; n3=n2->next; while(n2)//当n2为空的时候，那么此时的n1就指向的是反转后链表的头 { n2->next=n1; n1=n2; n2=n3; if(n3)//n3不能为空才能往下走,只要n3到空了，我们就没必要让n3继续走了 { n3=n3->next; } } //跳出循环 此时的n1就是反转后链表的头节点 return n1; } bool chkPalindrome(ListNode* A) { //1.找中间节点 ListNode*mid=findMidNode(A);//将链表A传过去 //2.根据中间节点反转后面的链表 ListNode*right=reverseList(mid);//将mid传过去，作为后半段头结点 //那么此时的right就是指向的是反转后链表的头结点 //3.从原链表和反转链表比较节点的值 ListNode*left=A;//让left赋值为头节点 //让right和left对应的指针进行一一比较 while(right)//我们以right为主，一但right遍历到空，我们就没必要进行比较了 { if(left->val!=right->val)//那么就不是回文结构了 { return false; } //走到这里就说明当前节点对应的大小是相等的，那么我们就进行下一对节点的比较 //让两个指针往后走 left=left->next; right=right->next; } //跳出循环，那么此时的right已经为空了 //那么这个链表的结构就是回文结构了 return true; } }; 先利用快慢指针找到中间节点
然后将中间节点之后的节点进行反转
然后将得到的反转链表和前一半的链表进行比较
每一对字节进行比较，看大小是否相同
题目七：相交链表
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ /* 1.如何判断链表是否相交 遍历两个链表若尾节点相同则链表一定相交 2.找相交链表的起始节点 */ /*思路一： 如果两个链表的节点个数不同的话，那么我们就补全少的那个， 让两个链表的个数一样，然后依次进行遍历 我们对两个链表的每个对应的节点进行判断，如果不相等的话 那么我们就进行换下一对节点进行判断 如果这两个链表有交点的话，那么这两个链表节点以及节点之后的节点都是相同的 */ /* 找两个链表的节点数差值， 假设一个链表是5个节点，一个是6个节点，那么差值就是1 那么我们让长的那个链表优先走一步，走一步之后，那么这两个链表就能开始进行比较了 总结：（1）找两个链表的节点数差值 （2）长链表先走差值数 （3）两个链表开始遍历，比较是否为同一个节点 */ typedef struct ListNode ListNode; struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { //创建两个指针分别指向两个链表 ListNode*l1=headA; ListNode*l2=headB; //计算两个链表的节点个数 int sizeA=0,sizeB=0; while(l1) { sizeA++; l1=l1->next; } while(l2) { sizeB++; l2=l2->next; } //求绝对值（差值） int gap=abs(sizeA-sizeB); //让长链表先走gap步 //但是我们不知道哪个链表长，哪个链表短 //创建两个指针，我们先随便进行定义，我们也不知道哪个链表长 ListNode *longList=headA; ListNode *shortList=headB; if(sizeA<sizeB) { longList=headB; shortList=headA; } //到这里我们就知道了长短链表了 while(gap--) { longList=longList->next; } //此时的longList和shortList在同一起跑线 //存在两种情况：链表相交或者是链表不相交 while(longList&&shortList)//两个指针不为空，那么我们就让他们往后走 { if(longList==shortList) { //链表相交了，我们就不用往后走了，我们直接返回此时节点的位置 return longList;//返回longList或者是shortList都行，因为此时的两个指针都在同一节点上 } //如果对应节点不相同的话，那么我们继续往后走 longList=longList->next; shortList=shortList->next; } //走到这里说明两个链表可能已经出现了空链表了，那么这两个链表就不存在相交的节点了 return NULL; } /* 总结： 我们要将两个链表的长度求出来 再利用长度求出两个链表的节点差值 定义出长链表和短链表 让长链表先走gap步，让两个链表指针重中之重重中之重在同一起点 */ 题目八：环形链表1
带环：从头结点开始遍历链表，链表没有结束的时候
就是链表的尾节点next节点不为空，指向当前链表的任意一个节点
特点就是死循环
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ /* pos就是入环节点位置 */ /* 创建快慢指针，若指针在运动的时候，指向的是同一个节点的话，那么就说明链表带环 如果链表不是带环的，那么快慢指针是绝对不会相遇的 */ //快慢指针相遇就说明链表带环 typedef struct ListNode ListNode; bool hasCycle(struct ListNode *head)//返回值是真假，看看是不是带环链表 { //创建快慢指针 ListNode*slow=head; ListNode*fast=head; while(fast&&fast->next) { //慢指针走一步，快指针走两步 slow=slow->next; fast=fast->next->next; if(slow==fast)//相遇了，就说明链表带环 { return true; } } //两个指针始终没有相遇 return false;//不带环 } 创建快慢指针，若指针在运动的时候，指向的是同一个节点的话，那么就说明链表带环
如果链表不是带环的，那么快慢指针是绝对不会相遇的
为什么慢指针走一步，快指针每次走两步，在带环链表中一定会相遇？
假设我们的链表是一个环，当slow进入环之后，此时slow和fast在环里开始了进行追逐
fast走两步，slow走一步，追逐过程中，距离N一直在减少，在环里肯定能相遇的
N是两个指针之间的距离
若N是偶数
那么每次slow走1步，fast走3步
那么距离变化就是这样子的：N N-2 N-4 N-6 …….. 0
当距离为0的时候，那么我们的两个指针就说明相遇了
如果N为奇数的话，假设N=7
7 5 3 2 1 -1 那么就会出现套圈的情况了
所以说N为偶数我们就相遇了，N为奇数我们就继续套圈
若出现套圈，那么fast和slow相隔的距离是C-1 因为已经相隔一圈的距离了，而且此时两个指针的实际距离是1
那么套圈后fast和slow是否还会相遇呢？
如果N是奇数，C-1也是奇数，那么永远不会相遇的
C-1是偶数继续套圈
在这个环内，slow走了L,fast走了L+xC+C-N
当slow到达开始的点，fast已经走了x圈了,而且比slow多走了C-N的距离
因为slow每次走一步
fast每次走三步，那么3slow=fast
那么3L=L+xC+C-N
那么我们得到2L=xC+C-N
2L=C（x+1）-N
当N为偶数时，C不可能为偶数
那么slow每次走一步，fast每次走两步，那么一定会相遇的
在使用快慢指针时，我们通常使用的是slow走一步，fast走两步
题目九：环形链表2
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ /* 通过快慢指针我们能判断链表是否带环 但是我们们不能判断环的节点在哪里 */ typedef struct ListNode ListNode; struct ListNode *detectCycle(struct ListNode *head) { //找环的相遇点 //头节点和相遇点开始遍历，每次都走一步 ListNode *slow=head; ListNode *fast=head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; if(fast==slow)//说明相遇了，那么此时的slow和fast都指向的是相遇点 { ListNode *pcur=head;//定义一个指针从头开始往后走 while(pcur!=slow)//如果pcur不等于slow，我们就进入循环一直遍历 { //走一步 pcur=pcur->next; slow=slow->next; } //跳出循环就说明了两个指针已经相等了 return pcur; } } //跳出循环，说明链表不带环 return NULL; } /* 思路：我们先利用快慢指针找到两个指针的相遇点 然后让头结点和相遇点的两个指针一起运动，每次一步 直到两个指针相遇了，那么就说明了相遇的位置就是我们要找的节点了 */ /*思考：为什么相遇点和头结点到入环节点的距离是相等的呢？*/ 为什么相遇点和头结点到入环节点的距离是相等的呢？
m是相遇点，我们要证明L=R-X
2*慢=快
慢：L+X
快:L+X+nR;
2(L+X)=L+X+nR
L=nR-X (n是快指针绕的几圈)
主要思路：让⼀个指针从链表起始位置开始遍历链表,同时让⼀个指针从判环时相遇点的位置开始绕环运⾏,两个指针都是每次均⾛⼀步,最终肯定会在⼊⼝点的位置相遇。
题目十：随机链表的复制
/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ //radom随机指向任意节点 /*大致思路： 1.在原链表基础上继续复制链表 2.置random指针 copy->random=pcur->random->next 3.复制链表和原链表断开 */ typedef struct Node Node; Node*buyNode(int x)//创建新的节点 { Node*newnode=(Node*)malloc(sizeof(Node)); newnode->val=x; newnode->next=newnode->random=NULL;//让节点的两个指针指向的都为空 return newnode; } void AddNode(Node*phead)//复制链表 { Node*pcur=phead; while(pcur)//直到pcur为空就停下 { Node*Next=pcur->next;//将原先链表节点后面的一个节点进行保存 //创建新的节点，尾插到pcur Node*newnode =buyNode(pcur->val);//创建了一个新的节点 //然后利用这个复制的节点进行尾插 pcur->next=newnode;//我们先让pcur的next指针指向刚刚创建的复制指针 //然后让这个新节点的下个指针指向我们pcur原先的next指向的节点，我们在之前已经进行了保存；了 newnode->next=Next; pcur=Next;//让pcur走到原先的节点，我们之前已经进行保存了 } } struct Node* copyRandomList(struct Node* head) { if(head==NULL) { return NULL; } //1.在原链表基础上继续复制链表 AddNode(head); //2.置random Node*pcur=head; while(pcur)//循环的去修改random指针 { Node*copy=pcur->next;//创建这么一个指针，这个指针一开始指向的是复制链表的第一个节点，因为我们上面已经将原链表的next指向改变了，就是如我们的图片所示，那么复制链表的第一个节点copy=pcur->next if(pcur->random!=NULL)//因为我们创建新的节点的时候，直接让我们的random指向的是空，那么我们现在只需要将原链表中不random不是指向的空进行处理 { copy->random=pcur->random->next; } pcur=copy->next;//我们让pcur顺着原来的链表进行遍历,但是我们的copy的下个节点恰好是我们原链表pcur下个节点 } //3.复制链表和原链表断开 pcur=head;//让pcur回到头节点 Node*newHead,*newTail;//创建两个指针指向新链表的头和尾 newHead=newTail=pcur->next;//pcur的下个节点就是新链表的头结点 while(pcur->next->next)//pcur每次走两步，走到原链表的下个节点，下个节点为空的话我们就跳出循环 { pcur=pcur->next->next;//让pcur走到pcur的下个节点的下个节点，就是原链表中pcur的下个节点 newTail->next=pcur->next;//pcur的下个节点就是对应的新链表中的下个节点 newTail=newTail->next;//让newTail走到新的节点 } return newHead; } 
进行完第一步的结果：
进行完第二步的结果：
