序次表和链表
1.线性表线性表（linearlist）是n个具有雷同特性的数据元素的有限序列。线性表是⼀种在现实中⼴泛使⽤的 数据布局，常⻅的线性表：序次表、链表、栈、队列、字符串...
线性表在逻辑上是线性布局，也就说是一连的⼀条直线。但是在物理布局上并不⼀定是一连的，线性 表在物理上存储时，通常以数组和链式布局的情势存储。
物理布局：数据在内存上的存储情势
逻辑布局：人为想象出来的数据的构造情势，如列队
2.序次表
序次表是⽤⼀段物理所在一连的存储单元依次存储数据元素的线性布局，⼀般情况下采⽤数组 存储。
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvNDU0NzllMjU1MDFlNDUyOWI0MGYwMjkyYjZhYjY0MmUucG5n
2.1.1序次表和数组的区别
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvM2VhYjRiNTA3ZjM2NDMyZDg2NzMyNWE1YjAzNGVkMjAucG5n
本质上是差不多的，只是加以修饰，序次表是对数组举行封装：布局体
2.1.2 序次表的分类
1.已知序次表的巨细：静态序次表
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvZTg3NDI5OTI5NzdjNDU5MWFhZWU4MzVjMjBkY2JhZmIucG5n
给小了不敷用，给大了会浪费
2.未知序次表的巨细：动态序次表
2.2.1序次表的初始化，烧毁
先创建3个文件，SeqList.h SeqList.c test.c 一个用来声明，一个用来实现，一个用来调试
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvOWFkNjY4MjNhOTM1NGZkMjkzMjBiMDgyMWFkMDM1ZTEucG5n
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvODliYzQ5YWFkZTJlNDNiZmIwMWM5YmQ3YTk2NmEzMTUucG5n
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvNjNjNTNjOTQ0OGIxNDU4OTkzZmI0ZmIzZmMzMzMwYzkucG5n
2.2.2序次表的增容
增容一样寻常2倍增长
增容分两种情况：
1：一连空间富足，直接扩容
2：一连空间不敷
1）重新找一块所在，分配富足的内存
2）拷贝数据到新的所在
3）烧毁旧所在
void SLCheckCapacity(SL* ps)
{
//判断空间是否充足
if (ps->capacity == ps->size)
{
//若capacity为0，给个默认值，否则x2倍
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDatatype*tmp =(SLDatatype*) realloc(ps->arr, newcapacity*sizeof(SLDatatype));
if (tmp == NULL)
{
perror("realloc");
exit(1);
}
ps->arr = tmp;
ps->capacity = newcapacity;
}
} 2.2.3序次表的插入
//插入数据，尾插
void SLPushBack(SL* ps, SLDatatype x)
{
assert(ps);
SLCheckCapacity(ps);
ps->arr = x;
ps->size++;
}
//插入数据，头插
void SLPushFront(SL* ps, SLDatatype x)
{
assert(ps);
SLCheckCapacity(ps);
//数据整体后移一位
for (int i = ps->size; i>0; i--)
{
ps->arr = ps->arr;
}
ps->arr = x;
ps->size++;
} 2.2.4序次表的删除
//删除数据，尾删
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);//有效个数要>0；
ps->arr = -1;
ps->size--;
}
//删除数据，头删
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
//将后面的数据往前提一个位置
for (int i = 0; i < ps->size-1; i++)
{
ps->arr = ps->arr;
}
ps->size--;
}
2.2.5在指定位置之前插入数据
//在指定位置之前插入数据
void SLInsert(SL* ps, SLDatatype x, int pos)//pos表示的是位置
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);//插入都要检查空间够不够
//pos及之后的位置集体向后移动1位
for (int i =ps->size-1 ; i>=pos ; i--)
{
ps->arr = ps->arr;
}
ps->arr = x;
ps->size++;
} 2.2.6删除指定位置的数据
//在指定位置删除数据
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
assert(ps->size);//顺序表不能为空
for (int i = pos; i < ps->size - 1; i++)
{
ps->arr = ps->arr;
}
ps->size--;
} 2.2.7查找数据
//查找数据(返回找到位置的下标，没有则返回-1)
int SLFind(SL* ps, SLDatatype x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr == x)
{
return i;
}
}
//没有找到
return -1;
} 2.2.8SeqList.h的代码
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//界说序次表布局
typedef int SLDatatype;
typedef struct SeqList
{
SLDatatype* arr;
int capacity;//空间巨细
int size;//有效元素个数
}SL;
//typedef struct SLDataList SL;
//初始化
void SLInit(SL* ps);
//烧毁
void SLDestroy(SL* ps);
//打印
void SLPrint(SL* ps);
//增容
void SLCheckCapacity(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);//pos体现的是位置
//在指定位置删除数据
void SLErase(SL* ps, int pos);
//查找数据(返回找到位置的下标，没有则返回-1)
int SLFind(SL* ps, SLDatatype x);
2.2.9SeqList.c的代码
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
//初始化
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->capacity = ps->size = 0;
}
//烧毁
void SLDestroy(SL* ps)
{
if (ps->arr)
{
free(ps->arr);
ps->arr = NULL;
}
ps->capacity = ps->size = 0;
}
//增容
void SLCheckCapacity(SL* ps)
{
//判定空间是否富足
if (ps->capacity == ps->size)
{
//若capacity为0，给个默认值，否则x2倍
int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SLDatatype*tmp =(SLDatatype*) realloc(ps->arr, newcapacity*sizeof(SLDatatype));
if (tmp == NULL)
{
perror("realloc");
exit(1);
}
ps->arr = tmp;
ps->capacity = newcapacity;
}
}
//插入数据，尾插
void SLPushBack(SL* ps, SLDatatype x)
{
assert(ps);
SLCheckCapacity(ps);
ps->arr = x;
ps->size++;
}
//插入数据，头插
void SLPushFront(SL* ps, SLDatatype x)
{
assert(ps);
SLCheckCapacity(ps);
//数据团体后移一位
for (int i = ps->size; i>0; i--)
{
ps->arr = ps->arr;
}
ps->arr = x;
ps->size++;
}
//打印
void SLPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr);
}
printf("\n");
}
//删除数据，尾删
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);//有效个数要>0；
ps->arr = -1;
ps->size--;
}
//删除数据，头删
void SLPopFront(SL* ps)
{
assert(ps);
assert(ps->size);
//将反面的数据往条件一个位置
for (int i = 0; i < ps->size-1; i++)
{
ps->arr = ps->arr;
}
ps->size--;
}
//在指定位置之前插入数据
void SLInsert(SL* ps, SLDatatype x, int pos)//pos体现的是位置
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);//插入都要查抄空间够不敷
//pos及之后的位置团体向后移动1位
for (int i =ps->size-1 ; i>=pos ; i--)
{
ps->arr = ps->arr;
}
ps->arr = x;
ps->size++;
}
//在指定位置删除数据
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);
assert(ps->size);//序次表不能为空
for (int i = pos; i < ps->size - 1; i++)
{
ps->arr = ps->arr;
}
ps->size--;
}
//查找数据(返回找到位置的下标，没有则返回-1)
int SLFind(SL* ps, SLDatatype x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr == x)
{
return i;
}
}
//没有找到
return -1;
}
2.3算法题训练
2.3.1移除元素
. - 力扣（LeetCode）
思绪：界说两个变量，src，dst。一开始都指向第一个元素。判定src的位置和val是否相当
相当：src++
不相当：nums=nums,src++,dst++
时间复杂度：O(N)
空间复杂度：O(1)
int removeElement(int* nums, int numsSize, int val) {
int dst = 0, src = 0;
while (src < numsSize)
{
if (nums == val)
{
src++;
}
else
{
nums = nums;
src++;
dst++;
}
}
return dst;
} 2.3.2删除有序数组中的重复项
. - 力扣（LeetCode）
思绪：界说两个变量，dst指向第一个位置，src指向下一个位置判定src和dst位置的数据
相当：src++
不相当：dst++，nums=nums,src++
//删除相等项，返回元素个数
int removeDuplicates(int* nums, int numsSize) {
int dst = 0, src = dst + 1;
while (src < numsSize)
{
if (nums == nums)
{
src++;
}
else
{
dst++;
nums = nums;
src++;
}
}
return dst + 1;
} 2.3.3归并两个有序数组
. - 力扣（LeetCode）
思绪：设3个位置，第一个为nums1末了一个有效元素（m-1），第二个为nums2末了一个元素(n-1)，第三个为nums1末了一个元素(N+M-1)，找1和2谁大，大的放第三个位置
竣事条件：要么l1<0，要么l2<0
l1<0：要把nums2中的数据循环放在nums1中
l2<0：不必剖析
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
int l1 = m - 1;
int l2 = n - 1;
int l3 = n + m - 1;
while (l1 > 0 && l2 > 0)
{
if (nums1 > nums2)
{
nums1 = nums1;
}
else
{
nums1 = nums2;
}
}
while (l2 >= 0)
{
nums1 = nums2;
}
} 2.4 序次表题目与思索
• 中央/头部的插⼊删除，时间复杂度为O(N)
• 增容须要申请新空间，拷⻉数据，开释旧空间。会有不⼩的斲丧。
• 增容⼀般是呈2倍的增⻓，势必会有⼀定的空间浪费。比方当前容量为100，满了以后增容到200， 我们 再继承插⼊了5个数据，后⾯没有数据插⼊了，那么就浪费了95个数据空间。
思 考：怎样办理以上题目呢？
3.单链表
链表是线性表的一种，链表是由一个一个的结点构成
每个结点内里有一个数据和一个指向下一个结点的指针构成
3.1申请新节点
//申请节点
SLTNode* SLTBuyNode(SLDataType x)
{
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
if (node == NULL)
{
perror("malloc fail");
exit(1);
}
node->date = x;
node->next = NULL;
return node;
} 3.2链表的打印
//链表的打印
void SLDPrint(SLTNode* phead)
{
SLTNode* pcur = phead;
while (pcur)
{
printf("%d-> ", pcur->date);
pcur = pcur->next;
}
printf("NULL\n");
} 3.3链表的尾插
形参的改变要影响实参，必须要传实参的所在
如果节点为空，申请的新节点就是尾节点，不为空，找到尾节点，再加进去
//尾插
void SLTPushBack(SLTNode** phead, SLDataType x)
{
//传的phead不能为空，不然解引用有问题
assert(phead);
//申请新节点
SLTNode* newnode = SLTBuyNode(x);
//尾节点->新节点
// 如果链表为空
if (*phead == NULL)
{
*phead = newnode;
}
else
{
//找尾节点
SLTNode* pcur = *phead;
while (pcur->next)
{
pcur->next;
}
pcur->next = newnode;
}
} 3.4链表的头插
申请一个新节点，让新节点的下一个节点指向原来的第一个辅导，再把原来的第一个节点位置指向新节点
//头插
void SLTPushFront(SLTNode** phead, SLDataType x)
{
//申请节点
SLTNode* newnode = SLTBuyNode(x);
newnode->next = *phead;
*phead = newnode;
} 3.5链表的尾删
要找到尾节点ptail，还要找其前一个结点prev，把prev的next置为NULL。
但是当链表只有一个数据时，找不到prev，prev原来为空还解引用会发生错误。
//尾删
void SLTPopBack(SLTNode** phead)
{
//链表为空：不可以删除
assert(phead && *phead);
//传的参数不能为空以及链表不能为空
//只有一个结点的情况，要删的就是头节点
if ((*phead)->next == NULL)
{
free(*phead);
*phead = NULL;
}
else
{
//找 prev ptail
SLTNode* ptail = *phead;
SLTNode* prev = NULL;
while (ptail->next)
{
prev = ptail;
ptail = ptail->next;
}
prev->next = NULL;
free(ptail);
ptail = NULL;
}
} 3.6链表的头删
把第二个结点存下来，然后开释掉第一个结点，再把第二个结点改为第一个结点
//头删
void SLTPopFront(SLTNode** phead)
{
assert(phead && *phead);
SLTNode* next = (*phead)->next;
free(*phead);
*phead = next;
} 大概先改头节点，再开释
SLTNode*del=*phead；
*phead=（*phead）->next；
free（del）；
del=NULL；
3.7链表的查找
//查找
SLTNode* SLTFind(SLTNode* phead, SLDataType x)
{
assert(phead);
SLTNode* pcur = phead;
while (pcur)
{
if (pcur->date == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
} 3.8在指定位置之前插⼊数据
找到指定位置pos的位置以及指定位置之前的位置prev，把要插入的数据放在他们中央
但是当只有一个数据的时间，它没有前一个位置，以是此时用头插
//在指定位置(pos)之前插⼊数据
void SLTInsert(SLTNode** phead, SLTNode* pos, SLDataType x)
{
assert(pos);//不能在NULL前插入
assert(phead);
SLTNode* newnode = SLTBuyNode(x);
if (*phead == pos)
{
SLTPushFront(phead, x);
}
else
{
//找prev：pos的前一个位置
SLTNode* prev = *phead;
while (prev->next != pos)
{
prev = prev->next;
}
newnode->next = pos;
prev->next = newnode;
}
} 3.9在指定位置之后插⼊数据
此时不须要知道头节点，由于我们可以通过pos的位置找到它反面的数据
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLDataType x)
{
//pos也不能为NULL
SLTNode* newnode = SLTBuyNode(x);
//pos newnode pos->next 使他们有所联系
newnode->next = pos->next;
pos->next = newnode;
} 3.10删除特定（pos）结点
找到pos的前一个结点，使它与pos的后一个结点产生接洽，再删去pos结点
但是如果他只有一个结点，我们找不到它前一个位置，以是相当于头删。
//删除pos结点
void SLTErase(SLTNode** phead, SLTNode* pos)
{
assert(phead && *phead);
assert(pos);
if (pos == *phead)
{
SLTPopFront(phead);
}
else
{
SLTNode* prev = *phead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}
3.11删除特定（pos）之后的结点
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{
assert(pos && pos->next);
//pos和他的下一个结点不能为空，不然没东西删
SLTNode* del = pos->next;
pos->next = pos->next->next;
free(del);
del = NULL;
} 3.12烧毁链表
每一个结点都得找到，设置一个pcur纪录当前结点，next为他的下一结点，循环把pcur删除
//销毁链表
void SListDestroy(SLTNode** phead)
{
assert(phead && *phead);
SLTNode* pcur = *phead;
while (pcur)
{
SLTNode* next = pcur->next;
free(pcur);
pcur = next;
}
*phead = NULL;
} 3.13单链表的算法题
3.13.1 移除链表元素
. - 力扣（LeetCode）
ListNode* removeElements(ListNode* head, int val) {
//创建新链表
ListNode*newHead,*newTail;
newHead=newTail=NULL;
//遍历链表
ListNode*pcur=head;
while(pcur)
{
//找值不为val的
if(pcur->val!=val)
{
//是否为空链表
if(newHead=NULL)
{
newHead=newTail=pcur;
}
else
{
newTail->next=pcur;
newTail=newTail->next;
}
}
pcur=pcur->next;
}
//此时插入的最后一个位置还有可能指向下一个位置是val，但是没有删除，所以要置为NULL
//但是有可能全部数据都是要删除的，此时对newTail指向就是对NULL解引用，要判断一下
if(newTail)
newTail->next=NULL;
return newHead;
}
};
3.13.2反转链表
. - 力扣（LeetCode）
思绪：设置3个指针，第一个为NULL，第二个指向第一个变量，第三个指向第二个变量，起首第二个指针指向第一个指针，然后第一个指针走到第二个指针，第二个指针指到第三个指针位置
class Solution {
public:
ListNode* reverseList(ListNode* head) {
//处理空链表
if(head==NULL)
{
return head;
}
ListNode*n1,*n2,*n3;
n1=NULL;n2=head;n3=head->next;
while(n2)
{
n2->next=n1;
n1=n2;
n2=n3;
if(n3)
n3=n3->next;
}
//此时n1就是链表反转后的头节点
return n1;
}
}; 3.13.3链表的中央节点
. - 力扣（LeetCode）
思绪：快慢指针，界说一个快指针fast，一个慢指针show，快指针每次走两步，慢指针每次走一步。
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvNDI0NWY1N2ZkMmY2NDU0Yzg5NzQ5MDUxMTg2MDBmMWIucG5n
class Solution {
public:
ListNode* middleNode(ListNode* head) {
//开始都指向第一个结点
ListNode*show=head,*fast=head;
//慢指针每次走一步
//快指针每次走两步
while(fast&&fast->next)//不能交换位置，不然可能对NULL进行解引用
{
show=show->next;
fast=fast->next->next;
}
//此时的show指向的位置就是中间结点
return show;
}
}; 3.13.4归并两个有序链表
. - 力扣（LeetCode）
思绪：创建一个新链表，再用两个指针分别指向这两个链表，谁小谁就放进去。当一个放完，把别的谁人链表直接添上去。
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
//处理链表为NULL的情况
if(list1==NULL)
{
return list2;
}
if(list2==NULL)
{
return list1;
}
//创建一个新链表
ListNode*newHead=NULL,*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
{
//L2尾插到新链表中
//是否为空链表
if(newHead==NULL)
{
newHead=newTail=L2;
}
else
{
newTail->next=L2;
newTail=newTail->next;
}
L2=L2->next;
}
}
//跳出循环，要么L1为NULL；要么L2为NULL
if(L1)
newTail->next=L1;
if(L2)
newTail->next=L2;
return newHead;
}
}; 大概
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
//处理链表为NULL的情况
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
{
//L2尾插到新链表中
newTail->next=L2;
newTail=newTail->next;
L2=L2->next;
}
}
//跳出循环，要么L1为NULL；要么L2为NULL
if(L1)
newTail->next=L1;
if(L2)
newTail->next=L2;
ListNode*ret=newHead->next;
free(newHead);
newHead=NULL;
return ret;
}
}; 3.13.5 链表分割
链表分割_牛客题霸_牛客网
思绪：弄一个小链表和一个大链表，遍历原链表，分别区分开来，然后再连起来。
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvZTBjZGI2NWZiMDJlNGUwZGI0NWQyZmRkNDM4NzA3N2UucG5n
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
// write code here
//创建两个非空链表：小链表和大链表
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可能是前面的数据，会陷入死循环
//所以要把大链表的最后一个数据的next置为NULL；
greaterTail->next=NULL;
//大小链表首尾相连
lessTail->next=greaterHead->next;
ListNode*ret=lessHead->next;
free(lessHead);
free(greaterHead);
lessHead=NULL;
greaterHead=NULL;
return ret;
}
}; 3.13.6 链表的回⽂布局
回文布局就是轴对称布局。
链表的回文布局_牛客题霸_牛客网
思绪：创建新的数组，遍历链表，把链表中的值放入数组中，在数组中判定是否为回文布局。
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
// write code here
int arr={0};
ListNode*pcur=A;
int i=0;
while(pcur)
{
arr=pcur->val;
pcur=pcur->next;
}
//i即结点的个数
int left=0;
int right=i-1;
while(left<right)
{
if(arr!=arr)
{
//不是回文
return false;
}
left++;
right--;
}
//是回文
return true;
}
}; 大概
先去通过快慢指针找中央结点，然后把中央结点之后的数据反转，再比力
ListNode*findMidNode(ListNode*phead)
{
ListNode*slow=phead;
ListNode*fast=phead;
while (fast&&fast->next) {
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
ListNode*reverseList(ListNode*phead)
{
ListNode*n1,*n2,*n3;
n1=NULL;n2=phead;n3=phead->next;
while(n2)
{
n2->next=n1;
n1=n2;
n2=n3;
if(n3)
n3=n3->next;
}
return n1;
}
bool chkPalindrome(ListNode* A) {
// write code here
//找中间节点
ListNode*mid =findMidNode(A);
//把中间后面链表反转
ListNode*right=reverseList(mid);
//从链表的头和反转链表的头进行比较
ListNode*left=A;
while(right)
{
if(left->val!=right->val)
{
return false;
}
left=left->next;
right=right->next;
}
return true;
}
};
3.13.7 相交链表
. - 力扣（LeetCode）
相交：两个链表重新开始遍历，尾结点是同一个结点
思绪：两个链表结点个数不愿定是一样的，以是同时开始遍历不能找到相交的起始位置。以是我们要先找两个链表的结点数差值，然后长链表开始先走差值步，然后同时开始遍历，比力是否为同一个结点，是的话就是相交的起始位置。
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode*l1=headA;*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;
}
//同时遍历
while(longList && shortList)
{
if(longList==shortList)
{
//链表相交
return longList;
}
longList=longList->next;
shortList=shortList->next;
}
//不相交
return NULL;
}
}; 3.13.8 环形链表I
. - 力扣（LeetCode）
带环：重新节点开始遍历，链表不会克制下来
思绪：快慢指针，快指针每次走两步，慢指针每次走一步，当慢指针追上快指针，也就是他们指向同一个位置的时间，就会带环。
你大概会迷惑为什么肯定会相遇，由于假设相差N步，他们每次收缩一步，早晚会相遇。
bool hasCycle(ListNode *head) {
//快慢指针
ListNode*slow=head;
ListNode*fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(fast==slow)
{
//相遇
return true;
}
}
//无相遇
return false;
}
}; 慢指针走一步，快指针走3，4，5...步都是会相遇，表明就不表明了，记得就行了。
简朴表明一下就是（假设此时快指针每次走三步）
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvNjg0MGIzMjA4NDkzNDg2ZDkxZTE5MGIzYzYzYmI1MmEucG5n
3.13.9 环形链表II
. - 力扣（LeetCode）
思绪：通过快慢指针找到链表的相遇点，在界说一个头节点，此时头节点和相遇点同时遍历，就能找到入环的位置，相遇的位置就是入环的位置。
ListNode *detectCycle(ListNode *head) {
//找环的相遇点
ListNode*slow=head;
ListNode*fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
//相遇链表一定带环
ListNode*pcur=head;
while(pcur!=fast)
{
pcur=pcur->next;
fast=fast->next;
}
return pcur;
}
}
//链表不带环
return NULL;
}
}; 证实：L=R-X
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvMjYwZGFlNTgxNGQ4NGI1YzkwOWUxNmE2YTdiNGFmNDIucG5n
3.13.10 随机链表的复制
. - 力扣（LeetCode）
思绪：
1.在原链表的根本上复制链表
2.置random链表
3.复制链表与原链表分开
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvZTI1YzQ5ZTMwNmYzNGJjNDlkNTljMzVlMWNjYmRlZTcuanBlZw==
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvNzJiYWYwYTZlZWNmNDcxYWFiNmY5Y2ZhZjUwMWIwZTUucG5n
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)
{
Node*Next=pcur->next;
//创建新节点，尾插到pcur后
Node*newnode=buyNode(pcur->val);
newnode->next=Next;
pcur->next=newnode;
pcur=Next;
}
}
Node* copyRandomList(Node* head) {
//在原链表上复制结点
AddNode(head);
//置random
Node*pcur=head;
while(pcur)
{
Node*copy=pcur->next;
if(pcur->random!=NULL)
{
copy->random=pcur->random->next;
}
pcur=copy->next;
}
//断开链表
pcur=head;
Node*newHead,*newTail;
newHead=newTail=pcur->next;
while(pcur->next->next)
{
pcur=pcur->next->next;
newTail->next=pcur->next;
newTail=newTail->next;
}
return newHead;
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金
页:
[1]