一，单链表
1，概念
链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的 指针链接次序实现的
链表有很多种，单链表就是其中一种，也是线性表的一种。
2，结构
对于链表中这样一个个内存分配不连续的结点，怎样将这些结点通过一种方式连接在一起呢？
这里就需要我们的链表了
就好比一节节车厢，通过车钩连接在一起，使得我们可以通过一个车厢来找到它的下一个车厢
所以链表是由结点组成的，而结点是由两部分组成：存储数据+指向下一个结点的指针。
（1）结点
与顺序表不同的是，链表⾥的每节"⻋厢"都是独⽴申请下来的空间，我们称之为“结点/结点”。
图中指针变量plist保存的是第⼀个结点的地址，我们称plist此时“指向”第⼀个结点，如果我们希望 plist“指向”第⼆个结点时，只需要修改plist保存的内容为0x0012FFA0。
链表中每个结点都是独⽴申请的（即需要插⼊数据时才去申请⼀块结点的空间），我们需要通过指针 变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。
代码构造：
struct SListNode
{
int data; //结点数据
struct SListNode* next; //指针变量⽤保存下⼀个结点的地址
}；3，性质
1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续
2、结点⼀般是从堆上申请的
3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续
当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数 据，也需要保存下⼀个结点的地址（当下⼀个结点为空时保存的地址为空）。
当我们想要从第⼀个结点⾛到最后⼀个结点时，只需要在当前结点拿上下⼀个结点的地址就可以了。
4，打印链表
void SLTPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
while (pcur != NULL)
{
printf("%d -> ", pcur->data);
pcur = pcur->next;//打印完后pcur指针要指向下一个结点处
}
printf("NULL\n");
}
代码实例：
这里针对的是整形数据，那么当我们想要保存的数据是字符型，浮点型呢？
四个解决方案：
（1）联合体
// 定义数据类型枚举
typedef enum {
TYPE_INT,
TYPE_CHAR,
TYPE_FLOAT,
TYPE_DOUBLE
} DataType;
// 定义数据联合体
typedef union {
int int_data;
char char_data;
float float_data;
double double_data;
} DataValue;
// 链表节点结构
typedef struct Node {
DataType type; // 数据类型标识
DataValue value; // 数据值
struct Node* next; // 下一个节点指针
} Node;（2）使用void*+类型指针
typedef struct Node {
void* data; // 通用数据指针
size_t data_size; // 数据大小
int data_type; // 数据类型标识
struct Node* next;
} Node;
Node* createNode(void* data, size_t size, int type) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = malloc(size);
memcpy(newNode->data, data, size);
newNode->data_size = size;
newNode->data_type = type;
newNode->next = NULL;
return newNode;
}（3）C++可以使用模板解决
typedef struct Node {
void* data; // 通用数据指针
size_t data_size; // 数据大小
int data_type; // 数据类型标识
struct Node* next;
} Node;
Node* createNode(void* data, size_t size, int type) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = malloc(size);
memcpy(newNode->data, data, size);
newNode->data_size = size;
newNode->data_type = type;
newNode->next = NULL;
return newNode;
}5，单链表的实现
头文件
#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;
//phead：头（首）结点
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);
//在指定位置之前插⼊数据
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 SListDestroy(SLTNode** pphead);申请新结点
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)
{
SLTNode* newnode = SLTBuyNode(x);
//链表为空，phead直接指向newnode结点
if (*pphead == NULL)
{
*pphead = newnode;
}
else {
//链表不为空，找尾结点，将尾结点和新节点连接起来
SLTNode* ptail = *pphead;
while (ptail->next)//等价于ptail->next != NULL
{
ptail = ptail->next;
}
//ptail newnode
ptail->next = newnode;
}
}（1）当链表为空，新结点就是首结点
（2）当链表不为空，先找到最后一个结点（尾结点），将尾结点的next指针指向newnode
代码实例：
通过调试我们发现，形参phead发生了变化，但是实参plist没有发生变化，所以在打印plist链表时，结果还是空链表。
原因是传值传参。
怎样辨别传值传参呢？最简单的就是只要看不到&这个符号，就是传值传参。
我们可以发现在这里我们想要的不是传值传参，我们想要通过修改形参来改变实参，所以我们这里要使用指针传参。
指针传参，即传递的参数是一个指针，我们可以通过下表来区分传递不同类型参数的不同情况。
plist本身是一个SLTNode*类型的一级指针，其要匹配的形参时*pphead（经过一次解引用），而&plist就是取出这个指针的地址，也就是二级指针，对应的形参就是pphead（未经过解引用），以及*plist就是对一级指针解引用，就是结点本身，其对应的形参就是**pphead（经过两次解引用）。
所以我们如果想要通过形参来直接改变实参本身，需要对plist进行修改，那么就需要传递plist的地址，也就是二级指针，用pphead来接收。
头插
需要改变头指针存放的地址，形参也是需要传递二级指针。新结点中存放原本头结点的指针，同时要将头指针重新指向新的指针。
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
assert(pphead);
SLTNode* newnode = SLTBuyNode(x);
//newnode *pphead
newnode->next = *pphead;
*pphead = newnode;
}尾删
尾删先要遍历一遍链表找到最后一个节点将其释放掉，还要找到倒数第二个节点将它的指针域中存的地址改为NULL。所以我们需要两个指针，一个用于遍历链表找到尾结点，一个用于找到倒数第二个结点，将其中保存的地址修改。注意空链表不能进行尾删，只有一个结点的链表尾删后会变成空链表，需要改变头指针存放的地址。
void SLTPopBack(SLTNode** pphead)
{
assert(pphead && *pphead);
//只有一个结点的情况
if ((*pphead)->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else {
SLTNode* prev = NULL;
SLTNode* ptail = *pphead;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
//prev ptail
prev->next = NULL;
free(ptail);
ptail = NULL;
}
}头删
空链表无法进行头删，要先判断链表是否为空。此外在进行头删的时候记得将原来的头节点释放掉，因此在改变头节点之前需要先保留原来头结点的地址，否则在更换完新的头节点后就找不到原来的头节点了
//头删
void SLTPopFront(SLTNode** pphead)
{
assert(pphead && *pphead);
SLTNode* next = (*pphead)->next;//*pphead为原本头结点指针，其中的next就是指向第二个结点，将其保存下来
free(*pphead);
*pphead = next;//将头结点的指针变为指向第二个结点
}查找
遍历链表，返回是要查找数据的结点的地址。
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
SLTNode* pcur = phead;
while (pcur)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
//未找到
return NULL;
}在指定位置之前插入数据
（1）pos是头结点的时候，思路就是头插
（2）pos不是头结点的时候，只需要遍历链表找到pos位置的前一个结点即可。
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
assert(pphead && pos);
//pos就是头结点
if (pos == *pphead)
{
//头插
SLTPushFront(pphead, x);
}
else {
SLTNode* newnode = SLTBuyNode(x);
//pos在头结点之后--->找pos前驱节点
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev newnode pos
newnode->next = pos;
prev->next = newnode;
}
}在指定位置之后插入数据
一般下，我们有两种赋值方法：
- 先让
newnode的指针域存储pos后一个节点的地址，再让pos的指针域存newnode的地址 - 借助中间变量先把
pos后面节点的地址保存起来，再让pos的指针域存newnode的地址，最后再让newnode的指针域存第一步中间变量中保存的地址。
注意：不能先让pos位置的next指向新结点，因为这种情况下，我们就会丢失指向pos原本下一个结点的指针，进而导致新结点的next无法改变。
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = SLTBuyNode(x);
//pos newnode pos->next
newnode->next = pos->next;
pos->next = newnode;
}删除pos结点
（1）pos是头结点，直接头删
（2）pos不是头结点
要考虑以上两种情况
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead && pos);
//要删除的结点刚好就是头结点---头删
if (pos == *pphead)
{
SLTPopFront(pphead);
}
else {
//prev
SLTNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
//prev pos pos->next
prev->next = pos->next;
free(pos);
pos = NULL;
}
}删除pos之后的结点
不能直接写成pos->next=pos->next->next，因为这样虽然将pos后的结点从链表中剔除，但是该结点是由malloc函数在堆上申请的，在不使用的时候需要free掉，否则会造成内存泄漏。
void SLTEraseAfter(SLTNode* pos)
{
assert(pos && pos->next);
//pos del del->next
SLTNode* del = pos->next;
pos->next = del->next;
free(del);
del = NULL;
}销毁链表
两个指针遍历链表，一个指针用于释放该结点，一个指针用于找到下一个结点
//销毁链表
void SListDestroy(SLTNode** pphead)
{
assert(pphead);
SLTNode* pcur = *pphead;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*pphead = NULL;
}二，链表的分类
链表的结构⾮常多样，以下情况组合起来就有8种（2x2x2）链表结构：
链表说明：
虽然有这么多的链表的结构，但是我们实际中最常⽤还是两种结构：单链表和双向带头循环链表
1.⽆头单向⾮循环链表：结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦ 结构，如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。
2.带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都是带头 双向循环链表。另外这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带来很多优势，实 现反⽽简单了，后⾯我们代码实现了就知道了。
三，链表题
移除链表元素
思路一：
找到值为val的结点并返回结点位置，删除pos位置的结点
递归法：
Node* removeElements(Node* head, int val)
{
if (head == NULL)
{
return NULL;
}
if (head->data == val)
{
Node* next = head->next;
free(head);
return next;
}
head->next = removeElements(head->next, val);
return head;
}双指针法：
Node* removeElements(Node* head, int val)
{
// 创建哑节点（dummy node），简化头节点删除操作
Node* dummy = (Node*)malloc(sizeof(Node));
dummy->next = head;
Node* prev = dummy; // 前驱指针
Node* curr = head; // 当前指针
while (curr != NULL) {
if (curr->data == val) {
// 删除当前节点
prev->next = curr->next;
free(curr);
curr = prev->next; // curr移动到下一个节点
} else {
// 继续前进
prev = curr;
curr = curr->next;
}
}
Node* newHead = dummy->next;
free(dummy);
return newHead;
}思路二：
创建新链表，将原来链表中值不为val的结点进行尾插
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)
{
ListNode*phead,*ptail;
phead=ptail=NULL;
ListNode*pcur=head;
while(pcur)
{
if(pcur->val!=val)
{
if(phead==NULL)
{
phead=ptail=pcur;
}
else
{
ptail->next=pcur;
ptail=ptail->next;
}
}
pcur=pcur->next;
}
return phead;
}
但是我们通过提交记录发现提交结果有错
我们可以发现最后的输出结果包含6，但我们不想让我们的结果包含6.
这是为什么？
因为我们没有将数据为5的结点中的next指针重置，所以5后面会重新链接到原来的链表。
所以我们需要对上面的代码进行优化
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
ListNode* removeElements(ListNode* head, int val) {
ListNode* newHead = NULL; // 新链表头
ListNode* newTail = NULL; // 新链表尾
ListNode* pcur = head; // 当前遍历指针
while (pcur != NULL) {
if (pcur->val != val) {
// 找到值不为val的节点，尾插到新链表
if (newHead == NULL) {
// 新链表为空，设置头和尾
newHead = newTail = pcur;
} else {
// 新链表不为空，尾插
newTail->next = pcur;
newTail = newTail->next;
}
}
pcur = pcur->next;
}
// 重要：将新链表的尾节点next置为NULL
if (newTail != NULL) {
newTail->next = NULL;
}
return newHead;
}补充：OJ代码的调试
如果没有会员，大家可以将代码复制到VS上进行调试。
反转链表
思路一：
创建新链表结点，遍历原链表结点，拿过来头插
创建新结点方法
ListNode* reverseList(ListNode* head) {
ListNode* newHead = NULL; // 初始化新链表头为空
ListNode* current = head; // 当前指针指向原链表头
while (current != NULL) { // 遍历原链表
// 创建新节点（复制原节点值）
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->val = current->val; // 复制节点值
// 头插到新链表
newNode->next = newHead; // 新节点指向当前新链表头
newHead = newNode; // 更新新链表头为新节点
current = current->next; // 移动到原链表下一个节点
}
return newHead; // 返回反转后的链表头
}原地反转
ListNode* reverseList(ListNode* head) {
ListNode* newHead = NULL; // 新链表头
ListNode* current = head; // 当前节点
while (current != NULL) {
ListNode* nextNode = current->next; // 保存下一个节点
// 头插：当前节点插入到新链表头部
current->next = newHead;
newHead = current;
current = nextNode; // 移动到下一个节点
}
return newHead;
}思路二：
创建三个指针，改变指针指向
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
if(head == NULL) { // 处理空链表情况
return head;
}
// 创建三个指针并初始化
ListNode* n1, *n2, *n3;
n1 = NULL; // 前驱指针，初始为NULL
n2 = head; // 当前指针，指向链表头
n3 = n2->next; // 后继指针，指向当前节点的下一个
while(n2) { // 遍历链表直到n2为NULL
n2->next = n1; // 反转当前节点的指针方向
n1 = n2; // n1移动到当前节点
n2 = n3; // n2移动到下一个节点
if(n3) // 如果n3不为空
n3 = n3->next; // n3继续向后移动
}
return n1; // n1最终成为新链表的头
}递归法：
struct ListNode* reverseList(struct ListNode* head) {
return reverse(NULL, head);
}
// 辅助递归函数
struct ListNode* reverse(ListNode* prev, ListNode* curr) {
if (curr == NULL) {
return prev;
}
ListNode* next = curr->next;
curr->next = prev;
return reverse(curr, next);
}链表的中间结点
思路一：
求链表的中间结点，除2求中间位置，返回中间对应的结点，需要考虑奇数和偶数的问题
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head)
{
ListNode* pcur=head;
ListNode* prev=head;
int k=0;
while(pcur)
{
k++;
pcur=pcur->next;
}
if(k%2==0)
{
k=k/2;
while(k)
{
prev=prev->next;
k--;
}
return prev;
}
else
{
k=k/2;
while(k)
{
prev=prev->next;
k--;
}
return prev;
}
}思路二：
快慢指针，慢指针每次走一步，快指针每次走两步。快指针走的路程是慢指针总路程的两倍：2*慢指针=快指针。
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head)
{
//创建快慢指针
ListNode*slow =head;
ListNode*fast= head;
while(fast&&fast->next)//这里不能交换顺序，因为fast指针可能为空，对空指针解引用会报错
{
slow=slow->next;
fast=fast->next->next;
}
//此时slow指向的就是中间结点
return slow;
}合并两个有序链表
思路一：
创建新链表，借用双指针判断两个链表中结点数据大小，再进行尾插。
（1）首先我们要判断链表为空的情况，此时要直接返回链表
（2）创建新链表，借用循环，比较两个链表结点数据的大小进行尾插
（3）判断两个链表谁先被遍历完，讨论两种情况
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
//处理链表为空
if(list1==NULL)
{
return list2;
}
if(list2==NULL)
{
return list1;
}
//创建空链表
ListNode*newhead,*newtail;
newhead=newtail=NULL;
ListNode* l1=list1;
ListNode* l2=list2;
while(l1&&l2)
{
if(l1->val<l2->val)
{
//l1尾插到新链表当中
if(newhead==NULL)
{
newhead=newtail=l1;
}
else
{
newtail->next=l1;
newtail=newtail->next;
}
l1=l1->next;
}
else//包含了数据相等的情况
{
if(newhead==NULL)
{
newhead=newtail=l2;
}
else
{
//数据相等时，不必单独讨论，将两个结点分别插入，只需要插入一个，再进入循环继续比较就行
newtail->next=l2;
newtail=newtail->next;
}
l2=l2->next;
}
}
//跳出循环，只有两种情况，l1为空/l2为空
if(l1)//l1不为空，说明l1还有剩余结点，继续连接
{
newtail->next=l1;
}
if(l2)
{
newtail->next=l2;
}
return newhead;
}上述代码我们发现十分冗余，这是为什么？
我们可以发现，我们在循环过程中，多次判断链表是否为空，那么我们可以直接创建一个非空链表。
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
//处理链表为空
if(list1==NULL)
{
return list2;
}
if(list2==NULL)
{
return list1;
}
//创建非空链表
ListNode*newhead,*newtail;
newhead=newtail=(ListNode*)malloc(sizeof(ListNode));
ListNode* l1=list1;
ListNode* l2=list2;
while(l1&&l2)
{
if(l1->val<l2->val)
{
//l1尾插到新链表当中
newtail->next=l1;
newtail=newtail->next;
l1=l1->next;
}
else
{
newtail->next=l2;
newtail=newtail->next;
l2=l2->next;
}
}
if(l1)
{
newtail->next=l1;
}
if(l2)
{
newtail->next=l2;
}
//newhead是哨兵结点，不存储实际数据，只是提供一个固定的起始点，真正的头结点是newhead->next
ListNode*ret=newhead->next;
free(newhead);
newhead=newtail=NULL;
return ret;
}另外，我们还可以用一种更简单的方式使上述代码更加简洁
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
struct ListNode dummy; // 用哨兵节点简化代码逻辑
struct ListNode* cur = &dummy; // cur 指向新链表的末尾
while (list1 && list2) {
if (list1->val < list2->val) {
cur->next = list1; // 把 list1 加到新链表中
list1 = list1->next;
} else { // 注：相等的情况加哪个节点都是可以的
cur->next = list2; // 把 list2 加到新链表中
list2 = list2->next;
}
cur = cur->next;
}
cur->next = list1 ? list1 : list2; // 三元运算符，list1为空时，就是list2，否则为list1
return dummy.next;
}
思路二：
递归，直接使用该函数当递归函数，递归边界就是一个链表为空，就返回另一个链表，如果两个链表都不为空，那么就比较两个链表中结点数据的大小，比较完后将较小的指针当作新链表的结点，再递归调用函数，将新链表的下一个结点指向递归后的结点
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if list1 is None: return list2 # 注：如果都为空则返回空
if list2 is None: return list1
if list1.val < list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
list2.next = self.mergeTwoLists(list1, list2.next)
return list2
链表分割
思路一：
创建两个新链表（大链表，小链表），遍历原链表将结点插入到对应的大小链表中，小的尾插到小链表中，大的尾插到大链表中，最后将大小链表首尾相连。
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));
ListNode*pcur=pHead;
while(pcur)
{
if(pcur->val<x)
{
lessTail->next=pcur;
lessTail=lessTail->next;
}
else{
greaterTail->next=pcur;
greaterTail=greaterTail->next;
}
pcur=pcur->next;
}
//大链表的next指针置为空（避免死循环）
greaterTail->next=NULL;
//大小链表首尾相连
lessTail->next=greaterHead->next;
ListNode*ret=lessHead->next;
free(lessHead);
free(greaterHead);
return ret;
}
};链表的回文结构
首先我们要知道什么叫回文数字和回文字符串，如1221，1331，abba这类形式都属于回文形式。
思路一：
创建新链表，保存原链表结点，反转新链表，遍历两个链表比较结点是否相同
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
if(A==NULL)
{
return false;
}
ListNode*p1,*p2,*pcur;
pcur=p1=A;
p2=NULL;
int k=0;
while(pcur)
{
ListNode*newNode=(ListNode*)malloc(sizeof(ListNode));
newNode->val=pcur->val;
newNode->next=p2;
p2=newNode;
pcur=pcur->next;
}
while(p1&&p2)
{
if(p1->val==p2->val)
{
k=1;
}
else {
k=0;
}
p1=p1->next;
p2=p2->next;
}
if(k==1)
{
return true;
}
else
{
return false;
}
}
};思路二：
创建数组（大小要足够），遍历原链表将结点的值一次存储在数组中，用数组判断回文结构的方法进行判断。
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
int arr[900]={0};
//遍历原链表，将链表中的值存储在数组中
int i=0;
ListNode* pcur=A;
while(pcur)
{
arr[i++]=pcur->val;
pcur=pcur->next;
}
int left=0;
int right=i-1;
while(left<right)
{
if(arr[left]!=arr[right])
{
return false;
}
left++;
right--;
}
return true;
}
};思路三：
找链表的中间结点，将中间结点当作新的链表的头结点，反转链表
class PalindromeList {
public:
ListNode* middleNode( ListNode* head)
{
//创建快慢指针
ListNode*slow =head;
ListNode*fast= head;
while(fast&&fast->next)//这里不能交换顺序，因为fast指针可能为空，对空指针解引用会报错
{
slow=slow->next;
fast=fast->next->next;
}
//此时slow指向的就是中间结点
return slow;
}
ListNode* reverseList( ListNode* head) {
if(head == NULL) { // 处理空链表情况
return head;
}
// 创建三个指针并初始化
ListNode* n1, *n2, *n3;
n1 = NULL; // 前驱指针，初始为NULL
n2 = head; // 当前指针，指向链表头
n3 = n2->next; // 后继指针，指向当前节点的下一个
while(n2) { // 遍历链表直到n2为NULL
n2->next = n1; // 反转当前节点的指针方向
n1 = n2; // n1移动到当前节点
n2 = n3; // n2移动到下一个节点
if(n3) // 如果n3不为空
n3 = n3->next; // n3继续向后移动
}
return n1; // n1最终成为新链表的头
}
bool chkPalindrome(ListNode* A)
{
//1,找中间结点
ListNode*mid=middleNode(A);
//2,反转以中间结点作为头的链表
ListNode*right=reverseList(mid);
//遍历原链表和反转后的链表，判断结点处的值是否相同
ListNode*left=A;
while(right)
{
if(left->val!=right->val)
{
return false;
}
left=left->next;
right=right->next;
}
return true;
}
};相交链表
思路一：
求两个链表的长度，先让长链表走长度差步，长短链表开始遍历比较结点的地址是否一样
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
//求两个链表的长度
ListNode*pcur1,*pcur2;
pcur1=headA;
pcur2=headB;
int m=0,n=0;
while(pcur1)
{
++m;
pcur1=pcur1->next;
}
while(pcur2)
{
++n;
pcur2=pcur2->next;
}
int gap=abs(m-n);//abs函数用于求绝对值
//让长链表先走gap步
ListNode*shortlist=headA;
ListNode*longlist=headB;
if(m>n)
{
shortlist=headB;
longlist=headA;
}
while(gap--)
{
longlist=longlist->next;
}
while(shortlist)
{
if(shortlist==longlist)
{
return shortlist;
}
shortlist=shortlist->next;
longlist=longlist->next;
}
return NULL;
}思路二：
通过数学方法我们让长短链表走完各自的路后，到对方的链表上，最后如果有相交结点，则两个指针走过的长度是一样的
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
struct ListNode* p = headA;
struct ListNode* q = headB;
while (p != q) {
p = p ? p->next : headB;//三元关系符
q = q ? q->next : headA;
}
return p;
}
环形链表I
思路一：
快慢指针，若链表内有环，则快慢指针一定会在链表内相遇
证明：
slow⼀次⾛⼀步，fast⼀次⾛2步，fast先进环，假设slow也⾛完⼊环前的距离，准备进环，此时fast 和slow之间的距离为N，接下来的追逐过程中，每追击⼀次，他们之间的距离缩⼩1步
追击过程中fast和slow之间的距离变化：
因此，在带环链表中慢指针⾛⼀步，快指针⾛两步最终⼀定会相遇。
那么，如果快指针每次走两步，三步或者更多步呢？
1，按照上⾯的分析，慢指针每次⾛⼀步，快指针每次⾛三步，此时快慢指针的最⼤距离为N，接下来的 追逐过程中，每追击⼀次，他们之间的距离缩⼩2步
追击过程中fast和slow之间的距离变化：
分析:
1、如果N是偶数，第⼀轮就追上了
2、如果N是奇数，第⼀轮追不上，快追上，错过了，距离变成-1，即C-1，进⼊新的⼀轮追击
a、C-1如果是偶数，那么下⼀轮就追上了
b、C-1如果是奇数，那么就永远都追不上
总结⼀下追不上的前提条件：N是奇数，C是偶数
2，
假设：
环的周⻓为C，头结点到slow结点的⻓度为L，slow⾛⼀步，fast⾛三步，当slow指针⼊环后， slow和fast指针在环中开始进⾏追逐，假设此时fast指针已经绕环x周。 在追逐过程中，快慢指针相遇时所⾛的路径⻓度:
fast: L+xC+C-N
slow：L
由于慢指针⾛⼀步，快指针要⾛三步，因此得出： 3 * 慢指针路程 = 快指针路程 ，即：
3L = L + xC + C − N
2L = (x + 1)C − N
对上述公式继续分析：由于偶数乘以任何数都为偶数，因此 ⼀定为偶数，则可推导出可能得情 况：
• 情况1：偶数=偶数-偶数
• 情况2：偶数=奇数-奇数
由step1中（1）得出的结论，如果N是偶数，则第⼀圈快慢指针就相遇了。
由step1中（2）得出的结论，如果N是奇数，则fast指针和slow指针在第⼀轮的时候套圈了，开始进 ⾏下⼀轮的追逐；当N是奇数，要满⾜以上的公式，则 (x+1)C 必须也要为奇数，即C为奇数，满⾜ （2）a中的结论，则快慢指针会相遇
因此，step1中的 N是奇数，C是偶数 ，既然不存在该情况，则快指针⼀次⾛3步最终⼀定也 可以相遇。
不成⽴ 快指针⼀次⾛4、5.....步最终也会相遇，其证明⽅式同上。
注意：虽然已经证明了快指针不论⾛多少步都可以满⾜在带环链表中相遇，但是在编写代码的时候 会有额外的步骤引⼊，涉及到快慢指针的算法题中通常习惯使⽤慢指针⾛⼀步快指针⾛两步 的⽅式。
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head)
{
ListNode*fast,*slow;
fast=head;
slow=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
return true;
}
}
return false;
}环形链表II
思路一：
快慢指针在环里一定会相遇，相遇点到入环起始结点的距离=链表头结点到入环起始结点的距离
证明：
说明:
H为链表的起始点，E为环⼊⼝点，M为与判环时候相遇点
设:环的⻓度为R，H到E的距离为L，E到M的距离为 X ，则：M到E的距离为 R-X 在判环时,快慢指针相遇时所⾛的路径⻓度:
fast: L+X + nR
slow：L+X
注意:
1.当慢指针进⼊环时，快指针可能已经在环中绕了n圈了，n⾄少为1
因为：快指针先进环⾛到M的位置,，最后⼜在M的位置与慢指针相遇
2.慢指针进环之后，快指针肯定会在慢指针⾛⼀圈之内追上慢指针
因为：慢指针进环后,快慢指针之间的距离最多就是环的⻓度,⽽两个指针在移动时,每次它们⾄今 的距离都缩减⼀步，因此在慢指针移动⼀圈之前快，指针肯定是可以追上慢指针的，⽽快指针速度是 满指针的两倍，因此有如下关系是：
2 * (L+X)=L+X+nR
L+X=nR
L=nR-X
L = (n-1)R+(R-X)
(n为1,2,3,4......，n的⼤⼩取决于环的⼤⼩，环越⼩n越⼤)
极端情况下，假设n=1，此时： L=R-X
即：⼀个指针从链表起始位置运⾏，⼀个指针从相遇点位置绕环，每次都⾛⼀步，两个指针最终会在 ⼊⼝点的位置相遇。
typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head)
{
ListNode*fast,*slow;
fast=head;
slow=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
//找到相遇的结点
if(slow==fast)
{
//相遇点和头结点同时遍历，只要结点相同就是入环起始结点
ListNode*pcur=head;
while(slow!=pcur)
{
pcur=pcur->next;
slow=slow->next;
}
return pcur;
}
}
return NULL;
}随机链表
思路一：
暴力求解
我们先要区分一下浅拷贝和深拷贝
浅拷贝：值拷贝
深拷贝：创建一个新对象，并递归地复制原对象中的所有成员（包括指针所指向的数据），使得新对象和原对象完全独立，修改其中一个不会影响另一个。
按照我们最初的思路，我们可以直接暴力求解，按照原链表的每一个结点开辟一个新的结点，就这样不断开辟新结点，然后尾插到新的链表中
新的链表头我们定义为copyHead,新的链表尾我们定义为copyTail，同时定义两个指针分别为phead和pcur指向原链表，不断开辟，复制，尾插即可。
但是我们的random指针如何设置呢？
我要从原链表的头结点开始设置，将pcur重新指向头结点，将新链表的头结点指向空，同时pcur指向下一个结点，复制其中的random指针，但是random指针指向的是上一个结点，所以需要遍历到random所指向的结点，十分麻烦。
思路二：
在原链表基础上拷贝结点
创捷指针pcur，只要pcur指向的结点不为空，就创建一个一模一样的结点尾插到原来的结点后，新结点的next指针指向pcur原来的下一个结点，并创建一个新的指针，pcur指向这个新的指针，不断重复上述操作
置random指针
上一步操作，我们没有对random指针进行操作，所以我们需要对random指针进行操作。
copy指向我们新开辟的结点，如果random指针不指向空时，就将cur- >random（指向的原链表中random结点所指向的结点）->next（random指向结点的next指针所指向的结点，即新开辟的结点）给到copy指向的random指针，随后copy指向下一个新开辟的结点，cur指向下一个原链表的结点。
断开新旧链表
我们需要创建两个新的指针指向新的开辟的结点（copyhead，copytail）
我们这里只需要将新结点的next指针指向新链表就行，原链表next指针指向新链表，但这并不影响新链表。
我们可以判断copytail的下一个结点不为空，就可以将pcur移动到原来链表的下一个结点，再将copytail的next指针修改为指向新链表。
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* head)
{
Node* pcur=head;
while(pcur)
{
Node*newnode=buynode(pcur->val);
Node* next=pcur->next;
newnode->next=next;
pcur->next=newnode;
pcur=next;
}
}
void setrandom(Node*head)
{
Node*pcur=head;
while(pcur)
{
Node* copy=pcur->next;
if(pcur->random)
{
copy->random=pcur->random->next;
}
pcur=copy->next;
}
}
struct Node* copyRandomList(struct Node* head)
{
if(head==NULL)
{
return head;
}
//在原链表的基础上拷贝结点并插入到在原链表中
Addnode(head);
//设置random
setrandom(head);
//断开新链表
Node*pcur=head;
Node*copyhead,*copytail;
copyhead=copytail=pcur->next;
while(copytail->next)
{
pcur=copytail->next;
copytail->next=pcur->next;
copytail=copytail->next;
}
return copyhead;
}