初阶数据结构—顺序表和链表

第一章：线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

 第二章：顺序表

2.1概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素。

//静态顺序表
#define N 10	//为了后续方便修改数组大小
typedef int SLDatatype;	//为了后续修改数组类型
 
//静态顺序表的缺点是：给小了不够用，给大了浪费
struct Seqlist
{
	SLDatatype a[N];
	size_t size;//记录有效数据
};

2. 动态顺序表：使用动态开辟的数组存储。

//动态顺序表
typedef int SLDatatype;
typedef struct Seqlist
{
	SLDatatype* a;//用指针指向malloc开辟的空间
	int size;//记录有效数据
	int capacity;//记录该空间容量大小，根据有效数据个数调整空间大小
}SL;

2.2 接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

顺序表头文件中各函数声明

因为后续要修改结构体，所以要传址调用。

//动态顺序表
typedef int SLDatatype;
typedef struct Seqlist
{
	SLDatatype* a;//用指针指向malloc开辟的空间
	int size;//记录有效数据
	int capacity;//记录该空间容量大小，根据有效数据个数调整空间大小
}SL;
 
//顺序表初始化
void SLInit(SL* psl);
 
//顺序表销毁
void SLDestroy(SL* psl);
 
//检查空间，满了增容
void SLCheckCapacity(SL* psl);
 
//顺序表打印
void SLPrint(SL* psl);
 
//STL命名风格
void SLPushBack(SL* psl, SLDatatype x);//顺序表尾插
void SLPushFront(SL* psl, SLDatatype x);//顺序表头插
void SLPopBack(SL* psl);//顺序表尾删
void SLPopFront(SL* psl);//顺序表头删
 
void SLInsert(SL* psl, int pos, SLDatatype x);//顺序表在pos位置插入x
void SLErase(SL* psl, int pos);//顺序表删除pos位置的值
 
//找到返回下标，找不到返回-1
int SLFind(SL* psl, SLDatatype x);//顺序表查找
void SLModify(SL* psl, int pos, SLDatatype x);//顺序表修改

顺序表各函数实现

顺序表初始化

void SLInit(SL* psl)//顺序表初始化
{
    //psl是指向顺序表这个结构体的指针，不能为空，所以所有操作顺序表的函数都要断言
	assert(psl);
	psl->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);
	if (psl->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	psl->size = 0;
	psl->capacity = 4;
}

顺序表销毁

void SLDestroy(SL* psl)//顺序表销毁
{
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

检查容量并增容的函数

因为头插尾插都需要考虑容量，所以需要一个检查容量并增容的函数

void SLCheckCapacity(SL* psl)//检查空间，满了增容
{
	assert(psl);
	if (psl->size == psl->capacity)
	{
		SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		psl->a = tmp;
		psl->capacity *= 2;
	}
}

顺序表尾插

void SLPushBack(SL* psl, SLDatatype x)//顺序表尾插
{
	assert(psl);
	SLCheckCapacity(psl);
	psl->a[psl->size++] = x;//在最后一个有效数据后插入数据
}

顺序表头插

void SLPushFront(SL* psl, SLDatatype x)//顺序表头插
{
	assert(psl);
	SLCheckCapacity(psl);
 
	int end = psl->size - 1;//原数组最后一个元素的下标
	while (end >= 0)
	{
		psl->a[end + 1] = psl->a[end];//原数组元素从后向前的顺序一次向后移动一步
		end--;
	}
	psl->a[0] = x;//数组开头插入数据
	psl->size++;//记录有效数据的变量++
}

顺序表尾删

void SLPopBack(SL* psl)//顺序表尾删
{
	assert(psl);
	//不需要处理最后的数据，因为不管置为多少都有歧义
	//所以直接将size(记录有效数据个数的变量)-1，就访问不到想删除的数据
 
	//温柔检查版本
	if (psl->size > 0)
		psl->size--;
	else
		printf("无数据，无法删除\n");
 
	//暴力检查版本
	assert(psl->size > 0);
	psl->size--;
}

顺序表头删

void SLPopFront(SL* psl)//顺序表头删
{
	assert(psl);
    assert(psl->size > 0);
    for (int i = 0; i < psl->size; i++)
    	psl->a[i] = psl->a[i + 1];
    
    psl->size--;
 
 
    //while循环版本一：
	int start = 0;
	//psl->size是元素个数，psl->size-1是数组最后一个元素的下标，< 就是到最后一个元素之前就停下
	//如果start<psl->size，那么start就可以指向最后一个元素，下方start+1就会越界
	while (start < psl->size - 1)
		psl->a[start++] = psl->a[start + 1];
    psl->size--;
    
    //while循环版本二：
	int start = 1;
	while (start<psl->size)//psl->size是元素个数，< 就是到最后一个元素停下
		psl->a[start - 1] = psl->a[start++];
    psl->size--;
}
 

顺序表在pos位置插入x

void SLInsert(SL* psl, int pos, SLDatatype x)//顺序表在pos位置插入x
{
	assert(psl);
	SLCheckCapacity(psl);//先检查数组是否满了，如果满了增容
	assert(pos >= 0 && pos <= psl->size);
    
    //for循环版本
	for (int i = psl->size; i > pos; i--)//下标从最后一个元素后面开始
		psl->a[i] = psl->a[i - 1];
 
	psl->a[pos] = x;
	psl->size++;
    
    //while循环版本
	int end = psl->size - 1;
	while (end >= pos)//下标从最后一个元素开始
		psl->a[end + 1] = psl->a[end--];
 
	psl->a[pos] = x;
	psl->size++;
}

顺序表头插、尾插改版 - 复用插入函数

void SLPushBack(SL* psl, SLDatatype x)//顺序表尾插
{
	SLInsert(psl, psl->size, x);//复用SLInsert函数
}
 
 
void SLPushFront(SL* psl, SLDatatype x)//顺序表头插
{
	SLInsert(psl, 0, x);//复用SLInsert函数
}

顺序表删除pos位置的值

void SLErase(SL* psl, int pos)//顺序表删除pos位置的值
{
	assert(psl);
	assert(0 <= pos && pos < psl->size);
 
	//版本一
	while (pos < psl->size - 1)//pos到倒数第二个元素停止
		psl->a[pos++] = psl->a[pos + 1];
	psl->size--;
 
	//版本二
	int start = pos + 1;
	while (start < psl->size)//start到最后一个元素停止
		psl->a[start - 1] = psl->a[start++];
	psl->size--;
}

顺序表头删、尾删改版 - 复用删除函数

void SLPopFront(SL* psl)//顺序表头删
{
    SLErase(psl, 0);//复用SLErase函数
}
 
void SLPopBack(SL* psl)//顺序表尾删
{
    SLErase(psl, psl->size - 1);//复用SLErase函数
}

顺序表查找

//找到返回下标，找不到返回-1
int SLFind(SL* psl, SLDatatype x)//顺序表查找
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
		if (x == psl->a[i])
			return i;
 
	return -1;
}

顺序表修改

void SLModify(SL* psl, int pos, SLDatatype x)//顺序表修改
{
	assert(psl);
    //温柔检查版本
	if (0 <= pos && pos < psl->size)
		psl->a[pos] = x;
	else
		printf("下标不存在\n");
 
    //暴力检查版本
	assert(0 <= pos && pos < psl->size);
	psl->a[pos] = x;
}

2.3 数组相关面试题

1. 原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

//思路：遍历原数组，把不等于val的值依次放到j下标位置（j从0开始）
//for循环
int removeElement(int* nums, int numsSize, int val) {
	int j = 0;
	for (int i = 0; i < numsSize; i++) 
		if (nums[i] != val) 
			nums[j++] = nums[i];
		
	return j;
}
 
 
//while循环
int removeElement(int* nums, int numsSize, int val) {
	int src = 0;
	int dest = 0;
	while (src < numsSize)
		if (nums[src] != val)
			nums[dest++] = nums[src++];
		else
			src++;//如果数组元素和val相等，遍历数组的指针要++
 
	return dest;
}

2. 删除排序数组中的重复项

给你一个非严格递增排列的数组nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。
元素的相对顺序应该保持一致 。然后返回nums中唯一元素的个数。
考虑nums的唯一元素的数量为k，你需要做以下事情确保你的题解可以被通过：
更改数组nums，使nums的前k个元素包含唯一元素，并按照它们最初在nums中出现的顺序排列。
nums的其余元素与nums的大小不重要。
返回 k 。
示例 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 。不需要考虑数组中超出新长度后面的元素。

//思路：直接把第一个元素拿下来，从数组的第二个元素开始比较。
//因为第一个元素无论是否重复都可以保留。
//比较时应该用当前元素和前一个元素比，否则无法处理最后的元素
int removeDuplicates(int* nums, int numsSize) {
    int j = 1; // 新下标
    int i = 1; // 原下标
    while (i < numsSize) {
        if (nums[i] != nums[i - 1])
            nums[j++] = nums[i++];
        else
            i++;
    }
    return j;//返回的下标是新数组最后元素的后一个，恰好也是新数组的个数
}

3. 合并两个有序数组。

给你两个按非递减顺序排列的整数数组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 中。

// 思路：倒着比较，倒着存，因为正向存会导致某些元素被覆盖。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
	int i = m - 1;     // nums1下标
	int j = n - 1;     // nums2下标
	int k = m + n - 1; // 合并后数组下标
	while (i >= 0 && j >= 0) {
		if (nums1[i] >= nums2[j])
			nums1[k--] = nums1[i--];
		else
			nums1[k--] = nums2[j--];
	}
 
	//nums2先遍历完说明数组合并成功，只有当nums2还未遍历完时才需要拷贝剩下数据
	while (j >= 0)
		nums1[k--] = nums2[j--];
}
 
//简便写法
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;     
    //i是nums1下标，j是nums2下标，k是新数组下标
    while (i >= 0 && j >= 0) 
        nums1[k--] = (nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--];
    
    while (j >= 0)
        nums1[k--] = nums2[j--];
}

2.4 顺序表的问题及思考

问题：

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

思考：如何解决以上问题呢？下面给出了链表的结构来看看。

第三章：链表

3.1 链表的概念及结构

3.3 链表的实现

单链表头文件中各函数声明（不带头单向非循环）

#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);
 
//头节点创建
SLTNode* BuyLTNode(SLTDataType x);
 
//需要修改头节点指针时就需要二级指针
//链表头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//链表尾插 - 一级指针版本
void SLTPushBack1(SLTNode* phead, SLTDataType x);
//链表尾插 - 二级指针版本
void SLTPushBack2(SLTNode** pphead, SLTDataType x);
//链表头删
void SLTPopFront(SLTNode** pphead);
//链表尾删
void SLTPopBack(SLTNode** pphead);
 
//链表查找
SLTNode* SLFind(SLTNode* phead, SLTDataType x);
 
//在pos之前插入
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//链表插入
//在pos之后插入
void SLInsertAfter(SLTNode* pos, SLTDataType x);//链表插入
 
void SLErase(SLTNode** pphead, SLTNode* pos);//删除pos位置的节点
void SLEraseAfter(SLTNode* pos);//删除pos位置的节点
 
void SLDestroy2(SLTNode** pphead);//释放链表 - 二级指针
void SLDestroy1(SLTNode* phead);//释放链表 - 一级指针

void SLTPrint(SLTNode* phead)//链表打印
{
	SLTNode* cur = phead;//cur指针指向头结点
	while (cur != NULL)//cur指针不为空，即cur没有指向最后一个节点
	{
		printf("%d->", cur->data);//打印当前节点数据成员data的值
		cur = cur->next;//将指针cur移动到下个节点
	}
	printf("NULL\n");
}

SLTNode* BuyLTNode(SLTDataType x)//创建新节点
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("BuyLTNode");
		return NULL;
	}
	newnode->data = x;
	newnode->next = NULL;
 
	return newnode;
}

void SLTPushFront(SLTNode** pphead, SLTDataType x)//链表头插
{
	//pphead是结构体指针变量的地址，不是结构体的地址。
	//所以要得到结构体的地址需要对pphead这个二级指针解引用。*pphead才是结构体的地址
	//不能断言*pphead。*pphead是节点指针，它为空说明是空链表，即使是空链表也需要能插入节点
	assert(pphead);//理论上pphead不会为空，但防止操作失误传空指针，需要断言
	
	SLTNode* newnode = BuyLTNode(x);//创建新节点
 
	//*pphead是头节点指针。
	//如果是空链表，那么*pphead为空，newnode是唯一节点，newnode->next为空，正确
	//如果不是空链表，那么*pphead指向原先头节点，newnode是现在第一节点，*pphead赋值给newnode->next，正确
	newnode->next = *pphead;
	*pphead = newnode;//头节点指针指向newnode
}

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
 
	SLTNode* newnode = BuyLTNode(x);//无论链表中是否有节点，都要创建节点
 
	//*pphead等效于结构体指针（即指向节点的指针）
	//非空链表
	if (*pphead != NULL)//如果该指针不为空，说明链表中有节点，所以要寻找最后一个节点
	{
		SLTNode* tail = *pphead;//创建尾结点指针，从头节点指针位置开始向后找
 
		while (tail->next != NULL)//如果tail指针的指针域不为空，说明不是尾节点，循环继续
			tail = tail->next;//将tail节点当前指针域赋值给tail指针，移动到下一个节点
 
		tail->next = newnode;//找到最后节点，将最后节点的指针域修改为新节点指针
	}
	//空链表
	else//这里*pphead为空，说明链表中没有节点，那么新节点就是头节点，*pphead就要指向该新节点
		*pphead = newnode;
}

void SLTPopBack(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);//空链表
	
	//版本一：创建上一节点指针
	if ((*pphead)->next == NULL)//节点指针域为空，说明只有一个节点
	{
		free(*pphead);//直接释放该节点
		*pphead = NULL;//将该节点指针置为空
	}
	else//链表不止一个节点
	{
		SLTNode* tail = *pphead;//创建尾指针寻找链表尾结点
		SLTNode* prev = NULL;//创建名为上一节点的 节点指针，用来寻找倒数第二个节点
		while (tail->next != NULL)//节点指针域不为空进入循环
		{
			prev = tail;//在尾结点指针向后移动之前，将当前位置地址赋值给 上一节点指针
			tail = tail->next;//尾结点指针向后移动
		}
		//上方尾结点指针找到最后一个节点时循环停止。此时尾指针指向最后一个节点，prev指针指向了倒数第二个节点
		free(tail);//将最后一个节点释放
		tail = NULL;//尾指针置为空
		prev->next = NULL;//将倒数第二个节点的指针域置为空
	}
 
 
	//版本二：如果cur指针指向节点的后面至少有2个节点才继续向后，否则停下
	if ((*pphead)->next == NULL)//只有一个节点
	{
		free(*pphead);//释放该节点
		*pphead = NULL;//头节点指针置为空
	}
	else//链表不止一个节点
	{
		SLTNode* cur = *pphead;//创建cur指针并指向头节点
 
		while ((cur->next)->next != NULL)//cur后面有2个节点才进入循环，即链表至少有3个节点。
			cur = cur->next;//cur移动到下一个节点。最终cur会指向倒数第二个节点
 
		free(cur->next);//此时cur指向倒数第二个节点，释放cur后面的节点
		cur->next = NULL;//再将当前节点的指针域置为空
	}
}

void SLTPopFront(SLTNode** pphead)//链表头删
{
	assert(pphead);
	assert(*pphead);//空链表 - 链表为空，不能头删
 
	SLTNode* del = *pphead;//创建del指针，指向头结点，即要删除的节点
 
	//让头节点指针往后移动一步，再删除del节点。
	//即使只有一个节点，头结点指针向后移动指向空，再删除del节点也是正确。
	*pphead = del->next;
	free(del);
}

SLTNode* SLFind(SLTNode* phead, SLTDataType x)//链表查找
{
	SLTNode* cur = phead;//创建cur指针并指向头节点
	while (cur != NULL)//当前指针不为空，说明不是空链表
	{
		if (cur->data == x)//如果找到指定节点
			return cur;//则返回该节点指针
 
		cur = cur->next;//没有找到指定节点，则cur指针向下一节点移动
	}
	return NULL;//如果头节点指针为空，说明是空链表
}

//链表插入 - 在pos之前插入
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);//pphead是头结点指针的地址，不是头结点指针，所以任何时候都不能为空
	assert(pos);
 
	if (pos == *pphead)//如果pos指向头结点
		SLTPushFront(pphead, x);//在头节点处创建新节点
 
	else
	{
		SLTNode* newnode = BuyLTNode(x);//创建新节点
		SLTNode* prev = *pphead;//创建前一节点指针，从头节点指针处开始
 
		while (prev->next != pos)//prev指针指向节点的下一节点不是pos节点，进入循环
			prev = prev->next;//prev指针移动到下一节点
 
		//出循环，prev指向了pos指向节点的前一节点
		prev->next = newnode;//prev节点指针域改为新节点指针
		newnode->next = pos;//新节点的指针域改为pos的节点指针
	}
}

//链表插入 - 在pos之后插入
void SLInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
 
	SLTNode* newnode = BuyLTNode(x);//创建新节点
	newnode->next = pos->next;//原pos后一节点的节点指针 存入 newnode节点的指针域
	pos->next = newnode;//pos的指针域修改为newnode节点指针
}

//链表删除（pos位置的值）
void SLErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);
	
	//如果pos指向头结点
	if (pos == *pphead)
		SLTPopFront(pphead);
	else
	{
		SLTNode* prev = *pphead;//创建上一节点指针，从头节点位置开始
		while (prev->next != pos)//prev指针指向节点的下一节点不是pos节点，进入循环
			prev = prev->next;//prev指针移动到下一节点
 
		//出循环，prev指向了pos节点的前一节点
		prev->next = pos->next;//prev节点指针域改为新节点的指针
		free(pos);//释放pos节点
	}
}

//链表删除（pos位置之后的值）
void SLEraseAfter(SLTNode* pos)
{
	//pos指向最后一个节点，无法删除
	assert(pos);
	assert(pos->next);
 
	SLTNode* next = pos->next;//创建next指针，指向pos的后一节点
	pos->next = next->next;//pos后一节点改为后二节点
	free(next);//释放后一节点
 
	//pos->next = pos->next->next;
	//此写法改完pos节点中指向下一节点的指针后，会导致找不到pos的下一节点
}

void SLDestroy2(SLTNode** pphead)//释放链表 - 二级指针
{
	assert(pphead);
	SLTNode* cur = *pphead;
 
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

struct ListNode* removeElements(struct ListNode* head, int val) {
	struct ListNode* cur = head;//当前节点指针
	struct ListNode* prev = NULL;//cur前一节点指针
 
	while (cur != NULL) {
		// 等于就删除
		if (cur->val == val) {
			// 头删
			if (prev == NULL) {//上一节点指针为空，说明cur指向了头节点
				cur = head->next;//cur移动到头节点的下一节点
				free(head);//释放当前头节点
				head = cur;//头节点移动到cur处（即下一节点）
			}
			// 非头删
			else {
				prev->next = cur->next;//因为要删除cur指向的节点，所以prev指向的前一节点的指针域要指向cur后面的节点
				free(cur);//释放cur节点
				cur = prev->next;//cur移动到prev的下一节点
			}
		}
		// 不等于就向下个节点移动
		else {
			prev = cur;//cur移动前先赋值给prev指针
			cur = cur->next;
		}
	}
	return head;
}

struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* cur = head;//遍历原链表的指针
    struct ListNode* newhead = NULL;//新链表头节点指针
    struct ListNode* tail = NULL;//新链表尾指针
 
    while (cur)
    {
        if (cur->val != val) //不等于val
        {
            if (tail == NULL)//新链表为空
                newhead = tail = cur;//新链表头尾结点指针同时指向第一个不等于val的节点
            else //新链表不为空
            {
                tail->next = cur;//链接下一个不等于val的节点
                tail = tail->next;//尾指针移动到下一节点，即新链表最后节点
            }
            cur = cur->next;//原链表指针移动到下一节点
            tail->next = NULL;//尾指针的next置为空
        }
        else //等于val
        {
            struct ListNode* del = cur;//删除当前节点
            cur = cur->next;//cur移动到下一节点
            free(del);
        }
    }
    return newhead;
}

struct ListNode* middleNode(struct ListNode* head) {
	struct ListNode* slow = head;
	struct ListNode* fast = head;
 
	// fast为空，说明fast指向最后一个节点的后面
	// fast->next为空，说明fast指向最后一个节点
	// 以上两种情况fast都遍历完链表，循环停下
	while (fast && fast->next) {
		slow = slow->next;
		fast = fast->next->next;
	}
	return slow;
}

struct ListNode* reverseList(struct ListNode* head) {
	if (head == NULL)
		return NULL;
 
	struct ListNode* n0 = NULL; //n0为最后节点的指针域
	struct ListNode* n1 = head;      
	struct ListNode* n2 = n1->next; 
	
	//n0和n1用于反转链表，n2用于迭代找到下节点
	while (n1) {
		n1->next = n0;
		// 迭代
		n0 = n1;
		n1 = n2;
		if (n2)
			n2 = n2->next;
	}
	return n0;
}

struct ListNode* reverseList(struct ListNode* head) {
	struct ListNode* cur = head;//cur指向目前要头插的节点
	struct ListNode* rhead = NULL;//新的头节点
 
	while (cur)
	{
		struct ListNode* next = cur->next;//next指向cur后一节点
 
		//头插
		cur->next = rhead;//cur指向的当前节点的指针域要指向新链表头结点，即头插
		rhead = cur;//头节点移动到新节点
		//迭代
		cur = next;//当前指向后移动
	}
	return rhead;
}

int kthToLast(struct ListNode* head, int k) {
    int kthToLast(struct ListNode* head, int k) {
        struct ListNode* slow = head;
        struct ListNode* fast = head;
 
        //fast走k步版本
        while (k--)
        {
            if (fast == NULL)
                return NULL;
 
            fast = fast->next;
        }
 
        while (fast)
        {
            slow = slow->next;
            fast = fast->next;
        }
        return slow->val;
        
 
        //fast走k-1步版本
        k = k - 1;
        while (k--)
        {
            if (fast == NULL)
                return NULL;
 
            fast = fast->next;
        }
 
        while (fast->next)
        {
            slow = slow->next;
            fast = fast->next;
        }
        return slow->val;
    }
}

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
	if (list1 == NULL && list2 == NULL) //两个都为空
		return NULL;
 
	struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));//创建哨兵位
	struct ListNode* tail = guard;//tail指向哨兵位
	while (list1 && list2) { //两个都不为空
		if (list1->val < list2->val) { //list1小
			tail->next = list1;//尾插list1
			list1 = list1->next;//list1向后移动
		}
		else { //list2小
			tail->next = list2;//尾插list2
			list2 = list2->next;//list2向后移动
		}
		tail = tail->next;//tail向后移动
	}
 
	//下方有两个功能：
	//1. 某一链表为空时，返回另一个链表
	//2. 上方while循环结束后，有一个链表已尾插完，将剩下另一个链表的节点尾插
	if (list1 == NULL)
		tail->next = list2;
	else if (list2 == NULL)
		tail->next = list1;
 
	struct ListNode* del = guard;
	guard = guard->next;
	free(del);
 
	return guard->next;
}

6. 链表分割 

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

思路：创建两个链表并且带哨兵位，第一个链表都是小于等于x的节点，第二个是大于x的节点。并链接两个链表。

ListNode* partition(ListNode* pHead, int x) {	
	ListNode* firstGuard, *firstTail, *secondGuard, *secondTail;
	firstGuard = firstTail = (ListNode*)malloc(sizeof(ListNode));//第一链表哨兵位和尾指针
	secondGuard = secondTail = (ListNode*)malloc(sizeof(ListNode));//第二链表哨兵位和尾指针
    
    ListNode* tail = pHead;
	while (tail) { //遍历原链表
		if (tail->val < x) { //小于x的节点
			firstTail->next = tail;//将小于x的节点尾插到第一链表
			firstTail = firstTail->next;//第一链表尾指针向后移动
		}
		else { //大于等于x的节点
			secondTail->next = tail;//将大于等于x的节点尾插到第二链表
			secondTail = secondTail->next;//第二链表尾指针向后移动
		}
		tail = tail->next;//原链表尾指针向后移动
	}
	
    //这里不需要判断第一链表和第二链表是否为空
	//如果第一链表为空，那么第一链表的哨兵位指向了第二链表的头节点
	//如果第二链表为空，那么第一链表尾结点的指针域指向第二链表的哨兵位的指针域，第二链表哨兵位的指针域为空
	firstTail->next = secondGuard->next;//链接第一第二链表
	secondTail->next = NULL;//将第二链表尾结点的指针域置为空
    pHead = firstGuard->next;//原链表头节点指向第一链表头节点
    free(firstGuard);
    free(secondGuard);
	return firstGuard->next;
}

7.  链表的回文结构

对于一个链表，请设计一个时间复杂度为O(n), 额外空间复杂度为O(1)的算法，判断其是否为回文结构。

思路：
用快慢指针找到中间节点；
从中间节点开始向后的部分逆置；
然后一个指针从头节点开始，一个指针从中间节点开始比较。

奇数个数的链表被分为两半后虽然节点个数不一样，但是前半段的最后节点依然指向中间点。

例如该链表1->2->3->2->1，逆置后，第一个2依然指向了3。（后半段链表遍历到倒数第二节点也可以）

bool chkPalindrome(ListNode* head) {
	// 用快慢指针找到中间节点。
	ListNode* fast = head;
	ListNode* slow = head;
	while (fast && fast->next) { //循环结束时，慢指针指向中间节点
		fast = fast->next->next;
		slow = slow->next;
	}
 
	// 从中间节点开始向后的部分逆置（逆置即三个指针迭代）
	ListNode* n1 = NULL;
	ListNode* n2 = slow;//n2指向第一个要逆置的节点，即中间节点
	ListNode* n3 = n2->next;
	while (n2) {
		n2->next = n1;
		// 迭代
		n1 = n2;
		n2 = n3;
		if (n3)
			n3 = n3->next;
	}
	// 迭代结束后，n1就是逆置后链表的头节点
 
	// 然后从一个指针从头节点开始，一个指针从中间开始比较
	while (n1) {
		if (head->val != n1->val)
			return false;
 
		n1 = n1->next;
		head = head->next;
	}
	return true;
}

8. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

方法一：

分别求出两个链表的长度LA和LB，长的先走差距步，在同时走，第一个相等的就是相交

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {                                    
    struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;
 
    int lenA = 1;
    int lenB = 1;
    while (tailA) { // 遍历A链表求出长度
        tailA = tailA->next;
        lenA++;
    }
 
    while (tailB) { // 遍历B链表求出长度
        tailB = tailB->next;
        lenB++;
    }
 
    if (tailA != tailB) // 如果A和B链表最后的节点不相等，说明两个链表不相交
        return NULL;
 
    int lenAbs = abs(lenA - lenB);
    // 假设A链表比B链表长。如果不是，修改长短指针
    struct ListNode* longList = headA;
    struct ListNode* shortList = headB;
    if (lenA < lenB) {
        longList = headB;
        shortList = headA;
    }
    while (lenAbs--) // 长的链表，让其指针先走差距步
        longList = longList->next;
 
    while (longList != shortList) {// 两个链表指针同时走，直到相等
        longList = longList->next;
        shortList = shortList->next;
    }
    return longList;
}

方法二：

让tailA和tailB两个指针遍历A和B链表。假设A链表相交之前的节点数是a，B链表相交之前的节点数是b，相交(含相交节点)之后的节点是c。那么pa指针遍历A和B链表走到相交节点的个数是a + c + b。pb指针遍历A和B链表走到相交节点的个数是b + c + a。节点数相等。

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    if (headA == NULL || headB == NULL) //某一链表为空，无相交节点
        return NULL;
                                    
    struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;
 
    while (tailA != tailB) {
        //将三目运算符的结果赋值给tailA和tailB
        tailA = (tailA == NULL) ? headB : tailA->next;//如果tailA不为空那么继续向后遍历，如果为空从B链表开始向后遍历
        tailB = (tailB == NULL) ? headA : tailB->next;//如果tailB不为空那么继续向后遍历，如果为空从A链表开始向后遍历
    }
    return tailA;
}

9. 环形链表

 给定一个链表，判断链表中是否有环。

思路：用快慢两个指针通知从链表头节点开始向后走。慢指针一次走一步，快指针一次走两步。相遇说明有环。进入环后，快指针和慢指针每次的距离都会缩短一步，最终一定能相遇。

bool hasCycle(struct ListNode* head) {
	struct ListNode* slow = head;
	struct ListNode* fast = head;
 
	// fast为空说明是空链表，fast->next为空说明是只有一个节点
	// 这两种情况都不可能是环形链表
	while (fast && fast->next) {
		fast = fast->next->next;
		slow = slow->next;
		if (slow == fast) {
			return true; // 如果相遇了，说明存在环
		}
	}
 
	return false; // 如果能正常退出循环，说明不存在环
}

10. 寻找环入口

给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 NULL

思路：先用快慢指针确认是否为环形链表。如果是，那么其中一个指针从头开始，另一个从相遇点开始，同时一次走一步。再次相遇时就是环入口。

结论及解释：

假设环外长度是a，环入口到环内相遇点的长度是b，相遇点到环入口的长度是c，n是圈数。

1. 慢指针一定在走完环内一周之前就会和快指针相遇，最慢也是刚好走完一周的情况。因为快慢指针在环内最长的距离就是一圈，并且快指针速度慢指针2倍，所以慢指针走完一圈时，快指针走完两周，此时相遇。慢指针走过的距离就是a+b。
2. 快指针在和慢指针相遇之前至少走完环内一圈。当快指针第一次经过相遇点时，慢指针肯定还没到此位置，所以一定是快指针至少第二次到相遇点时他们才会相遇。快指针走过的距离是a+b+n*(c+b)。
3. 无论何时停下（包括相遇时）快指针走过的长度是慢指针的2倍。因为快指针速度是慢指针2倍。2*(a+b)=a+b+n*(c+b)。

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
 
    while (fast && fast->next) { //判断是否为环形链表
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) { //如果是
            slow = head;//slow回到头
            while (slow != fast) { //同时一次走一步，相等就是环入口
                slow = slow->next;
                fast = fast->next;
            }
            return fast;
        }
    }
    return NULL;
}

11. 随机链表的复制

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

思路：
1. 先复制每个节点再插入到对应节点后面，形成新链表，此时不管random指向，因为需要完成新链表后才能复制random。比如第二节点的random指向最后节点，此时新链表未完成，那么复制的节点的random就无法指向它应该指向的位置。
2. 修改复制节点的random指向。复制节点的random指向是它对应节点的random的next（如果对应节点的random指向空那就置为空）
3. 将链表重新链接。把所有复制节点链接。

插入复制节点后的新链表

struct Node* copyRandomList(struct Node* head) {
    if (head == NULL)
        return NULL;
    
    //1.复制节点并插入到对应节点后
    for (struct Node* cur = head; cur != NULL; cur = cur->next->next)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        copy->next = cur->next;
        cur->next = copy;
    }
 
    //2.调整复制节点的random指向
    for (struct Node* cur = head; cur != NULL; cur = cur->next->next)
    {
        struct Node* copy = cur->next;
        copy->random = (cur->random == NULL) ? NULL : cur->random->next;
    }
 
    //3.将复制节点链接
    struct Node* copyHead = head->next;
    for (struct Node* cur = head; cur != NULL; cur = cur->next)
    {
        struct Node* copy = cur->next;
        cur->next = copy->next;
        copy->next = (copy->next == NULL) ? NULL : copy->next->next;
    }
    return copyHead;
}

3.5 双向链表的实现

双向链表头文件中各函数声明（带头双向循环）

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
 
typedef int LTDataType;
//带头双向循环链表
//尾结点的next指向哨兵位；
//哨兵位的prev指向尾结点；
//哨兵位的next指向头结点。
 
//如果链表为空，那么哨兵位的next指向它自己，prev也指向它自己
typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;
 
LTNode* LTInit();//初始化
void LTPrint(LTNode* phead);//打印
 
bool LTEmpty(LTNode* phead);//判断链表是否为空
void LTPushBack(LTNode* phead, LTDataType x);//尾插
void LTPushFront(LTNode* phead, LTDataType x);//头插
void LTPopBack(LTNode* phead);//尾删
void LTPopFront(LTNode* phead);//尾删
 
LTNode* LTFind(LTNode* phead, LTDataType x);//查找
void LTInsert(LTNode* pos, LTDataType x);//在pos之前插入
void LTErase(LTNode* pos);//删除
void LTDestroy(LTNode* phead);//释放

双向链表各函数实现

创建新节点

该函数要在最上面位置，因为下方函数都需要用到该函数，编译器只会向上找。如果函数的定义是在调用函数的后面（下面）则需要在调用之前声明函数的定义，否则不需要事先声明。

LTNode* BuyLTNode(LTDataType x) //创建新节点
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("BuyLTNode");
		return NULL;
	}
	newnode->data = x;
	newnode->prev = NULL;
	newnode->next = NULL;
 
	return newnode;
}

初始化

如果要给该函数设置参数，那么需要二级指针才能完成修改节点指针，但其他函数都可以通过一级指针实现功能。所以为了保持格式一致，该函数不设置参数，而是返回哨兵位的节点指针。

LTNode* LTInit() //初始化
{
    //初始化是让哨兵位的prev和next指向自己
    //因为目前没有其他节点
	LTNode* phead = BuyLTNode(-1);//-1是自己给哨兵位设置的值，实际不储存有效数据
	phead->prev = phead;
	phead->next = phead;
 
	return phead;
}

双向链表打印

void LTPrint(LTNode* phead) //打印
{
	assert(phead);
	printf("Guard<==>");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<==>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

双向链表尾插

void LTPushBack(LTNode* phead, LTDataType x) //尾插
{
	assert(phead);
 
	LTNode* newnode = BuyLTNode(x);
 
	LTNode* tail = phead->prev;//创建尾结点，哨兵位的prev就是指向了尾结点
	tail->next = newnode;//尾结点的next指向newnode
	newnode->prev = tail;//newnode的prev指向尾结点
	newnode->next = phead;//newnode的next指向哨兵位
	phead->prev = newnode;//哨兵位的prev指向newnode
}

双向链表头插

void LTPushFront(LTNode* phead, LTDataType x) //头插
{
	assert(phead);
 
	//版本一：不记录头节点，但需要注意链接时的顺序。需要先链接newnode和原头节点
	LTNode* newnode = BuyLTNode(x);
	//如果为空链表，那么phead->next还是phead，newnode->next需要指向phead，
    //因为它是唯一节点；如果不为空phead->next是原先第一节点
	newnode->next = phead->next;
	//如果为空链表，那么phead->next还是phead，phead->prev需要指向newnode，
    //因为它是唯一节点；如果不为空phead->next是原先第一节点
	phead->next->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;
 
 
	//版本二：记录头节点
	LTNode* newnode = BuyLTNode(x);
	LTNode* first = phead->next;
 
	newnode->next = first;
	first->prev = newnode;
	phead->next = newnode;
	newnode->prev = phead;
}

判断链表是否为空

头删和尾删都需要用该函数，因为只剩哨兵位时不能再删除节点。

bool LTEmpty(LTNode* phead) //判断链表是否为空
{
	assert(phead);
	return phead->next == phead;//返回表达式的结果。为真说明是空链表，为假说明是非空链表
}

双向链表尾删

void LTPopBack(LTNode* phead)//尾删
{
	assert(phead);
	//LTEmpty链表为空返回真；非空返回假。
	//assert用于检查条件是否为真。如果条件为假，则会触发断言失败，并打印相关信息。
    //如果条件为真，则继续执行后续代码。
	//所以通过取反操作符 !将函数的返回值取反
	assert(!LTEmpty(phead));
 
	LTNode* tail = phead->prev;//tail是最后第一节点
	LTNode* tailPrev = tail->prev;//tailPrev是倒数第二个节点
	free(tail);
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

双向链表头删

void LTPopFront(LTNode* phead)//头删
{
	assert(phead);
	assert(!LTEmpty(phead));
 
	LTNode* first = phead->next;//first是第一个节点
	LTNode* second = first->next;//second是第二个节点
	second->prev = phead;
	phead->next = second;
}

双向链表查找

LTNode* LTFind(LTNode* phead, LTDataType x)//查找
{
	assert(phead);
 
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
			return cur;
 
		cur = cur->next;
	}
	return NULL;
}

在pos之前插入

void LTInsert(LTNode* pos, LTDataType x)//在pos之前插入
{
	assert(pos);
 
	LTNode* newnode = BuyLTNode(x);
	LTNode* prev = pos->prev;
 
	//位置顺序：prev newnode pos
	newnode->prev = prev;
	prev->next = newnode;
	newnode->next = pos;
	pos->prev = newnode;
}

双向链表头插、尾插改版 - 复用插入函数

void LTPushBack(LTNode* phead, LTDataType x) //尾插
{
    //当pos指向phead时，在pos之前插入相当于在phead->prev位置插入。phead->prev就是尾结点
	LTInsert(phead, x);
}
 
 
void LTPushFront(LTNode* phead, LTDataType x) //头插
{
	LTInsert(phead->next, x);//phead->next是原头结点
}

删除pos位置的节点

void LTErase(LTNode* pos)//删除
{
	//此函数有缺陷，如果pos等于哨兵位，链表被破坏。可以选择传哨兵位并判断pos!=phead
	assert(pos);
 
	//位置顺序：prev pos next
	LTNode* posPrev = pos->prev;
	LTNode* posNext = pos->next;
 
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}

双向链表头删、尾删改版 - 复用删除函数

void LTPopFront(LTNode* phead)//头删
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->next);
}
 
void LTPopBack(LTNode* phead)//尾删
{
	assert(phead);
	assert(!LTEmpty(phead));
	LTErase(phead->prev);
}

释放双向链表

void LTDestroy(LTNode* phead)//释放
{
	assert(phead);
 
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
}