ARTICLE DETAIL

建站实战干货

来自一线的建站与推广经验沉淀，每一条都经过真实交付验证。

首页 / 资讯中心 / 正文

数据结构的算法分析与线性表＜1＞

2026/8/2 18:14:56 拓冰建站 浏览量
数据结构的算法分析与线性表＜1＞

一、算法分析：

由于语句执行一次的实际所需时间与机器的软硬件有关，则算法分析是针对语句执行次数，而非执行时间。

时间复杂度

计算时间复杂度：

常量阶

如果算法中的n是固定的，或者说n是常数，或者时间复杂度计算出来是一个常数（1万，1亿都是），不随n变化，则直接T(n)=O(1).

对于对数阶的情况，可以先列出最后t次的i值，因为i最终要>n才能跳出循环，则假设等于n，即可算出最终的次数t

空间复杂度

因为一般情况下空间较为充足，则一般只讨论时间复杂度

抽象数据类型ADT 

二、线性表

        A、线性表的定义与特点


        线性表意思n个相同数据类型的数据元素的有序列表
        其中的元素个数n定义为线性表的长度，当n=0时，称之为空表，对于非空的线性表或线性结构，特点：
                存在唯一的“第一个”与“最后一个”的数据元素
                除第一个元素外，结构中的每个数据元素均只有一个前驱
                除最后一个外，结构中的每个数据均只有一个后继


        B、线性表的顺序表示与实现


                1、顺序表的初始化：

#include <stdio.h>#define MAXSIZE 100
typedef int ElemType;//顺序表定义
typedef struct{ElemType data[MAXSIZE];int length;
}SeqList;//顺序表初始化
void initList(SeqList *L)
{L->length = 0;
}int main(int argc, char const *argv[])
{//声明一个顺序表并初始化SeqList list;initList(&list);printf("初始化成功，目前长度占用%d\n",list.length);printf("目前占用内存%zu字节\n", sizeof(list.data));return 0;
}

                2、顺序表的尾部添加元素：

                

#include <stdio.h>#define MAXSIZE 100
typedef int ElemType;//顺序表定义
typedef struct{ElemType data[MAXSIZE];int length;
}SeqList;//顺序表初始化
void initList(SeqList *L)
{L->length = 0;
}//尾部添加元素
int appendElem(SeqList *L, ElemType e)
{if (L->length>=MAXSIZE){printf("顺序表已满\n");return 0;}L->data[L->length] = e;L->length++;return 1;
}int main(int argc, char const *argv[])
{//声明一个线性表并初始化SeqList list;initList(&list);printf("初始化成功，目前长度占用%d\n",list.length);printf("目前占用内存%zu字节\n", sizeof(list.data));appendElem(&list, 88);return 0;
}

                3、顺序表的遍历：

#include <stdio.h>#define MAXSIZE 100
typedef int ElemType;//顺序表定义
typedef struct{ElemType data[MAXSIZE];int length;
}SeqList;//顺序表初始化
void initList(SeqList *L)
{L->length = 0;
}//尾部添加元素
int appendElem(SeqList *L, ElemType e)
{if (L->length>=MAXSIZE){printf("顺序表已满\n");return 0;}L->data[L->length] = e;L->length++;return 1;
}//遍历
void listElem(SeqList *L)
{for (int i = 0; i < L->length; i++){printf("%d ", L->data[i]);}printf("\n");
}int main(int argc, char const *argv[])
{//声明一个线性表并初始化SeqList list;initList(&list);printf("初始化成功，目前长度占用%d\n",list.length);printf("目前占用内存%zu字节\n", sizeof(list.data));appendElem(&list, 88);appendElem(&list, 45);appendElem(&list, 43);appendElem(&list, 17);listElem(&list);return 0;
}

将顺序表的全部值，从头到尾打印一遍


                4、循环表的插入元素：

#include <stdio.h>#define MAXSIZE 100
typedef int ElemType;//顺序表定义
typedef struct{ElemType data[MAXSIZE];int length;
}SeqList;//顺序表初始化
void initList(SeqList *L)
{L->length = 0;
}//尾部添加元素
int appendElem(SeqList *L, ElemType e)
{if (L->length>=MAXSIZE){printf("顺序表已满\n");return 0;}L->data[L->length] = e;L->length++;return 1;
}//遍历
void listElem(SeqList *L)
{for (int i = 0; i < L->length; i++){printf("%d ", L->data[i]);}printf("\n");
}//插入数据
int insertElem(SeqList *L, int pos, ElemType e)
{if(L->length >= MAXSIZE){printf("表已经满了\n");return 0;}if (pos < 1 || pos > L->length){printf("插入位置错误\n");return 0;}if (pos <= L->length){for (int i = L->length-1; i >= pos-1; i--){L->data[i+1] = L->data[i];}L->data[pos-1] = e;L->length++;	}return 1;
}int main(int argc, char const *argv[])
{//声明一个线性表并初始化SeqList list;initList(&list);printf("初始化成功，目前长度占用%d\n",list.length);printf("目前占用内存%zu字节\n", sizeof(list.data));appendElem(&list, 88);appendElem(&list, 67);appendElem(&list, 40);appendElem(&list, 8);appendElem(&list, 23);listElem(&list);insertElem(&list, 2, 18);listElem(&list);return 0;
}

                5、对表与插入位置进行检测


 

                6、表中的删除元素：

                对于删除的数的定义与传值，利用指针
                利用指针意思是通过形参来改变实参，因为这样可以对函数外的值进行改变

                对于表的情况检测：

#include <stdio.h>#define MAXSIZE 100
typedef int ElemType;//顺序表定义
typedef struct{ElemType data[MAXSIZE];int length;
}SeqList;//顺序表初始化
void initList(SeqList *L)
{L->length = 0;
}//尾部添加元素
int appendElem(SeqList *L, ElemType e)
{if (L->length>=MAXSIZE){printf("顺序表已满\n");return 0;}L->data[L->length] = e;L->length++;return 1;
}//遍历
void listElem(SeqList *L)
{for (int i = 0; i < L->length; i++){printf("%d ", L->data[i]);}printf("\n");
}//插入数据
int insertElem(SeqList *L, int pos, ElemType e)
{if(L->length >= MAXSIZE){printf("表已经满了\n");return 0;}if (pos < 1 || pos > L->length){printf("插入位置错误\n");return 0;}if (pos <= L->length){for (int i = L->length-1; i >= pos-1; i--){L->data[i+1] = L->data[i];}L->data[pos-1] = e;L->length++;	}return 1;
}//删除数据
int deleteElem(SeqList *L, int pos, ElemType *e)
{if(L->length == 0){printf("空表\n");return 0;}if (pos < 1 || pos > L->length){printf("删除数据位置有误\n");return 0;}*e = L->data[pos-1];if (pos < L->length){for (int i = pos; i < L->length; i++){L->data[i-1] = L->data[i];}}L->length--;return 1;
}int main(int argc, char const *argv[])
{//声明一个线性表并初始化SeqList list;initList(&list);printf("初始化成功，目前长度占用%d\n",list.length);printf("目前占用内存%zu字节\n", sizeof(list.data));appendElem(&list, 88);appendElem(&list, 67);appendElem(&list, 40);appendElem(&list, 8);appendElem(&list, 23);listElem(&list);insertElem(&list, 1, 18);listElem(&list);ElemType delData;deleteElem(&list, 2, &delData);printf("被删除的数据为：%d\n", delData);listElem(&list);return 0;
}

                7、表的查找：


（对于动态分配：使用malloc函数来对于堆中开辟空间，创造一个数据）
[使用注意事项：
1、需要包含标准库头文件<stdlib.h>
2、一般返回viod* 通用数据类型指针，则使用时需要进行数据强转换，可结构体或int之类
3、函数会分配指定字节数的内存空间，并且返回一个指向这块内存起始位置的void*指针。要是内存分配失败，就会返回NULL。

#include <stdio.h>
#include <stdlib.h>int main() {int* ptr;// 分配4个int大小的内存空间ptr = (int*)malloc(4 * sizeof(int));
//int型强转，if (ptr == NULL){printf("内存分配失败\n");return 1;}// 使用分配的内存for (int i = 0; i < 4; i++) {ptr[i] = i * 10;}for (int i = 0; i < 4; i++) {printf("ptr[%d] = %d\n", i, ptr[i]);}// 释放内存free(ptr);return 0;
}


4、在使用malloc时，一定要使用sizeof操作符来计算所需内存的大小。就像前面的例子，sizeof(int)能根据不同的系统环境确定一个整数所占的字节数。（利于代码移植）
申请的空间是：  指针  指向的那块内存申请的空间
5、通过malloc分配的内存，在使用完毕后必须调用free()函数进行释放，以避免出现内存泄漏的问题。
6、malloc分配的内存中可能包含之前残留的数据，也就是这些内存不会被自动初始化。如果需要初始化为 0，可以使用calloc函数。]

                8、表的动态分配地址初始化：

                对于此时L所接收的是地址，返回的也是，则对于之前的函数是直接在栈区进行创建数据，使用时对地址进行操作需要使用&（取地址符），现在直接返回地址，则可直接对返回的值进行操作：

#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 100
typedef int ElemType;//顺序表定义
typedef struct{ElemType *data;int length;
}SeqList;//顺序表初始化－动态分配内存
SeqList* initList()
{SeqList *L = (SeqList*)malloc(sizeof(SeqList));L->data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);L->length = 0;return L;
}//尾部添加元素
int appendElem(SeqList *L, ElemType e)
{if (L->length>=MAXSIZE){printf("顺序表已满\n");return 0;}L->data[L->length] = e;L->length++;return 1;
}//遍历
void listElem(SeqList *L)
{for (int i = 0; i < L->length; i++){printf("%d ", L->data[i]);}printf("\n");
}//插入数据
int insertElem(SeqList *L, int pos, ElemType e)
{if(L->length >= MAXSIZE){printf("表已经满了\n");return 0;}if (pos < 1 || pos > L->length){printf("插入位置错误\n");return 0;}if (pos <= L->length){for (int i = L->length-1; i >= pos-1; i--){L->data[i+1] = L->data[i];}L->data[pos-1] = e;L->length++;	}return 1;
}//删除数据
int deleteElem(SeqList *L, int pos, ElemType *e)
{if(L->length == 0){printf("空表\n");return 0;}if (pos < 1 || pos > L->length){printf("删除数据位置有误\n");return 0;}*e = L->data[pos-1];if (pos < L->length){for (int i = pos; i < L->length; i++){L->data[i-1] = L->data[i];}}L->length--;return 1;
}//查找数据位置
int findElem(SeqList *L, ElemType e)
{if (L->length == 0){printf("空列表\n");return 0;}for (int i = 0; i < L->length; i++){if(L->data[i] == e){return i + 1;}}return 0;
}
int main(int argc, char const *argv[])
{//声明一个线性表并初始化SeqList *list = initList();printf("初始化成功，目前长度占用%d\n",list->length);printf("目前占用内存%zu字节\n", sizeof(list->data));appendElem(list, 88);appendElem(list, 67);appendElem(list, 40);appendElem(list, 8);appendElem(list, 23);listElem(list);insertElem(list, 1, 18);listElem(list);ElemType delData;deleteElem(list, 2, &delData);printf("被删除的数据为：%d\n", delData);listElem(list);printf("%d\n", findElem(list, 40));return 0;
}


        C、线性表的链式表达与实现


                1、定义：

        它是一种物理存储单元上非连续、非顺序的存储结构 ，数据元素的逻辑顺序通过链表中的指针链接次序实现。由一系列结点组成，结点可在运行时动态生成。


                2、结点：

        每个结点包含两部分，一是存储数据元素的数据域 ，用于存放具体数据；二是存储下一个结点地址的指针域 （最后一个指针域为NULL）（在双向链表中还有指向前驱结点的指针域 ），通过指针将各个结点连接起来，形成链表结构。


                3、单链表-存储结构：

使用结构体来编写节点。
typedef  int  ElemType;
typedef  struct  node
{ElemType  data;//数据域struct  node  *next;//指针域
}Node; //别名



                4、单链表-初始化：

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;typedef struct node{ElemType data;struct node *next;
}Node;//初化链表
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}int main(int argc, char const *argv[])
{Node *list = initList();return 0;
}


                5、单链表-头插法

头插法-插入节点，创建新结点并且将指针域值变换
为什么是头插法，因为传入的一直是第一个结点

#include <stdio.h>
#include <stdlib.h>typedef int ElemType;typedef struct node{ElemType data;struct node *next;
}Node;//初化链表
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//头插法
int insertHead(Node* L, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}int main(int argc, char const *argv[])
{Node *list = initList();insertHead(list, 10);insertHead(list, 20);return 0;
}

                6、单链表-遍历

#include <stdio.h>
#include <stdlib.h>typedef int ElemType;typedef struct node{ElemType data;struct node *next;
}Node;//初化链表
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//头插法
int insertHead(Node* L, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//遍历
void listNode(Node* L)
{Node *p = L->next;while(p != NULL){printf("%d　", p->data);p = p->next;}printf("\n");
}int main(int argc, char const *argv[])
{Node *list = initList();insertHead(list, 10);insertHead(list, 20);insertHead(list, 30);listNode(list);return 0;
}

                7、单链表-尾插法


        尾插法就是在末尾插入结点
        但尾插法需要先知道尾部值的地址，则需要通过遍历找到最后结点指针域是NULL的

Node* get_tail(Node  *L)
{Node  *p=L;while( p -> next !=  NULL)
{p = p -> next ;
}return  p;
}

        然后再返回新的尾结点

            

#include <stdio.h>
#include <stdlib.h>typedef int ElemType;typedef struct node{ElemType data;struct node *next;
}Node;//初化链表
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//头插法
int insertHead(Node* L, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//遍历
void listNode(Node* L)
{Node *p = L->next;while(p != NULL){printf("%d　", p->data);p = p->next;}printf("\n");
}//获取尾部结点
Node*  get_tail(Node  *L)
{Node *p = L;while(p->next != NULL){p = p->next;}return p;
}//尾插法
Node* insertTail(Node *tail, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;tail->next = p;p->next = NULL;return p;
}int main(int argc, char const *argv[])
{Node *list = initList();Node *tail = get_tail(list);tail  = insertTail(tail, 10);tail  = insertTail(tail, 20);tail  = insertTail(tail, 30);listNode(list);return 0;
}

              8、单链表-在指定位置插入数据

#include <stdio.h>
#include <stdlib.h>typedef int ElemType;typedef struct node{ElemType data;struct node *next;
}Node;//初化链表
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//头插法
int insertHead(Node* L, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//遍历
void listNode(Node* L)
{Node *p = L->next;while(p != NULL){printf("%d ", p->data);p = p->next;}printf("\n");
}//获取尾部结点
Node*  get_tail(Node  *L)
{Node *p = L;while(p->next != NULL){p = p->next;}return p;
}//尾插法
Node* insertTail(Node *tail, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;tail->next = p;p->next = NULL;return p;
}//指定位置插入
int insertNode(Node *L, int pos, ElemType e)
{//用来保存插入位置的前驱节点Node *p = L;int i = 0;//遍历链表找到插入位置的前驱节点while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}//要插入的新节点Node *q = (Node*)malloc(sizeof(Node));q->data = e;q->next = p->next;p->next = q;return 1;
}int main(int argc, char const *argv[])
{Node *list = initList();Node *tail = get_tail(list);tail  = insertTail(tail, 10);tail  = insertTail(tail, 20);tail  = insertTail(tail, 30);listNode(list);insertNode(list, 2, 15);listNode(list);return 0;
}


                9、单链表-删除节点

#include <stdio.h>
#include <stdlib.h>typedef int ElemType;typedef struct node{ElemType data;struct node *next;
}Node;//初化链表
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//头插法
int insertHead(Node* L, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//遍历
void listNode(Node* L)
{Node *p = L->next;while(p != NULL){printf("%d ", p->data);p = p->next;}printf("\n");
}//获取尾部结点
Node*  get_tail(Node  *L)
{Node *p = L;while(p->next != NULL){p = p->next;}return p;
}//尾插法
Node* insertTail(Node *tail, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;tail->next = p;p->next = NULL;return p;
}//指定位置插入
int insertNode(Node *L, int pos, ElemType e)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}Node *q = (Node*)malloc(sizeof(Node));q->data = e;q->next = p->next;p->next = q;return 1;
}//删除节点
int deleteNode(Node *L, int pos)
{//要删除节点的前驱Node *p = L;int i = 0;//遍历链表，找到要删除节点的前驱。while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}if(p->next == NULL){printf("要删除的位置错误\n");return 0;}//q指向要删除的节点Node *q = p->next;//让要删除节点的前驱指向要删除节点的后继p->next = q->next;//释放要删除节点的内存空间free(q);return 1;
}int main(int argc, char const *argv[])
{Node *list = initList();Node *tail = get_tail(list);tail  = insertTail(tail, 10);tail  = insertTail(tail, 20);tail  = insertTail(tail, 30);listNode(list);insertNode(list, 2, 15);listNode(list);deleteNode(list, 2);listNode(list);return 0;
}

注意删除节点，一定要释放所删除节点的空间（因为是在堆区中创建的）


                10、单链表-获取链表长度

#include <stdio.h>
#include <stdlib.h>typedef int ElemType;typedef struct node{ElemType data;struct node *next;
}Node;//初化链表
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//头插法
int insertHead(Node* L, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//遍历
void listNode(Node* L)
{Node *p = L->next;while(p != NULL){printf("%d ", p->data);p = p->next;}printf("\n");
}//获取尾部结点
Node*  get_tail(Node  *L)
{Node *p = L;while(p->next != NULL){p = p->next;}return p;
}//尾插法
Node* insertTail(Node *tail, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;tail->next = p;p->next = NULL;return p;
}//指定位置插入
int insertNode(Node *L, int pos, ElemType e)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}Node *q = (Node*)malloc(sizeof(Node));q->data = e;q->next = p->next;p->next = q;return 1;
}//删除节点
int deleteNode(Node *L, int pos)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}if(p->next == NULL){printf("要删除的位置错误\n");return 0;}Node *q = p->next;p->next = q->next;free(q);return 1;
}//获取链表长度
int listLength(Node *L)
{Node *p = L;int len = 0;while(p != NULL){p = p->next;len++;}return len;
}int main(int argc, char const *argv[])
{Node *list = initList();Node *tail = get_tail(list);tail  = insertTail(tail, 10);tail  = insertTail(tail, 20);tail  = insertTail(tail, 30);listNode(list);insertNode(list, 2, 15);listNode(list);deleteNode(list, 2);listNode(list);printf("%d\n", listLength(list));return 0;
}


                        和遍历相似

                11、单链表-释放链表

                释放链表：释放除头结点之后的所有节点

#include <stdio.h>
#include <stdlib.h>typedef int ElemType;typedef struct node{ElemType data;struct node *next;
}Node;//初化链表
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//头插法
int insertHead(Node* L, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//遍历
void listNode(Node* L)
{Node *p = L->next;while(p != NULL){printf("%d ", p->data);p = p->next;}printf("\n");
}//获取尾部结点
Node*  get_tail(Node  *L)
{Node *p = L;while(p->next != NULL){p = p->next;}return p;
}//尾插法
Node* insertTail(Node *tail, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;tail->next = p;p->next = NULL;return p;
}//指定位置插入
int insertNode(Node *L, int pos, ElemType e)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}Node *q = (Node*)malloc(sizeof(Node));q->data = e;q->next = p->next;p->next = q;return 1;
}//删除节点
int deleteNode(Node *L, int pos)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}if(p->next == NULL){printf("要删除的位置错误\n");return 0;}Node *q = p->next;p->next = q->next;free(q);return 1;
}//获取链表长度
int listLength(Node *L)
{Node *p = L;int len = 0;while(p != NULL){p = p->next;len++;}return len;
}//释放链表
void freeList(Node *L)
{Node *p = L->next;Node *q;while(p != NULL){q = p->next;free(p);p = q;}L->next = NULL;
}int main(int argc, char const *argv[])
{Node *list = initList();Node *tail = get_tail(list);tail  = insertTail(tail, 10);tail  = insertTail(tail, 20);tail  = insertTail(tail, 30);listNode(list);insertNode(list, 2, 15);listNode(list);deleteNode(list, 2);listNode(list);printf("%d\n", listLength(list));freeList(list);printf("%d\n", listLength(list));return 0;
}

        D、线性表的应用


                1、单链表--现只给出了头指针，在不改变链表的情况下查找到其中的倒数第K个位置上的data域的值

#include <stdio.h>
#include <stdlib.h>typedef int ElemType;typedef struct node{ElemType data;struct node *next;
}Node;//初化链表
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//头插法
int insertHead(Node* L, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//遍历
void listNode(Node* L)
{Node *p = L->next;while(p != NULL){printf("%d ", p->data);p = p->next;}printf("\n");
}//获取尾部结点
Node*  get_tail(Node  *L)
{Node *p = L;while(p->next != NULL){p = p->next;}return p;
}//尾插法
Node* insertTail(Node *tail, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;tail->next = p;p->next = NULL;return p;
}//指定位置插入
int insertNode(Node *L, int pos, ElemType e)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}Node *q = (Node*)malloc(sizeof(Node));q->data = e;q->next = p->next;p->next = q;return 1;
}//删除节点
int deleteNode(Node *L, int pos)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}if(p->next == NULL){printf("要删除的位置错误\n");return 0;}Node *q = p->next;p->next = q->next;free(q);return 1;
}//获取链表长度
int listLength(Node *L)
{Node *p = L;int len = 0;while(p != NULL){p = p->next;len++;}return len;
}//释放链表
void freeList(Node *L)
{Node *p = L->next;Node *q;while(p != NULL){q = p->next;free(p);p = q;}L->next = NULL;
}//查找倒数第k个节点
int findNodeFS(Node *L, int k)
{Node *fast = L->next;Node *slow = L->next;for (int i = 0; i < k; i++){fast = fast->next;}while(fast != NULL){fast = fast->next;slow = slow->next;}printf("倒数第%d个节点值为：%d\n", k, slow->data);return 1;
}int main(int argc, char const *argv[])
{Node *list = initList();Node *tail = get_tail(list);tail  = insertTail(tail, 10);tail  = insertTail(tail, 20);tail  = insertTail(tail, 30);tail  = insertTail(tail, 40);tail  = insertTail(tail, 50);tail  = insertTail(tail, 60);tail  = insertTail(tail, 70);listNode(list);findNodeFS(list, 3);return 0;
}

                2、单链表--对于两个不同长度链表，其末尾是相同的几个结点，要找到最开始相同的结点的指针域


        获取两个链表长度进行相减得到步差，这时就也可以使用快慢指针从两个链表中进行寻找，同时走到同一个地址时，则该的结点为要求节点


                3、单链表--删除绝对值相同的节点

#include <stdio.h>
#include <stdlib.h>typedef char ElemType;typedef struct node{ElemType data;struct node *next;
}Node;//初化链表
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//初始化节点（带节点数据域参数）
Node* initListWithElem(ElemType e)
{Node *node = (Node*)malloc(sizeof(Node));node->data = e;node->next = NULL;return node;
}//头插法
int insertHead(Node* L, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//遍历
void listNode(Node* L)
{Node *p = L->next;while(p != NULL){printf("%c ", p->data);p = p->next;}printf("\n");
}//获取尾部结点
Node*  get_tail(Node  *L)
{Node *p = L;while(p->next != NULL){p = p->next;}return p;
}//尾插法
Node* insertTail(Node *tail, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;tail->next = p;p->next = NULL;return p;
}//尾插法（节点）
Node* insertTailWithNode(Node *tail, Node *node)
{tail->next = node;node->next = NULL;return node;
}//指定位置插入
int insertNode(Node *L, int pos, ElemType e)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}Node *q = (Node*)malloc(sizeof(Node));q->data = e;q->next = p->next;p->next = q;return 1;
}//删除节点
int deleteNode(Node *L, int pos)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}if(p->next == NULL){printf("要删除的位置错误\n");return 0;}Node *q = p->next;p->next = q->next;free(q);return 1;
}//获取链表长度
int listLength(Node *L)
{Node *p = L;int len = 0;while(p != NULL){p = p->next;len++;}return len;
}//释放链表
void freeList(Node *L)
{Node *p = L->next;Node *q;while(p != NULL){q = p->next;free(p);p = q;}L->next = NULL;
}//查找倒数第k个节点
int findNodeFS(Node *L, int k)
{Node *fast = L->next;Node *slow = L->next;for (int i = 0; i < k; i++){fast = fast->next;}while(fast != NULL){fast = fast->next;slow = slow->next;}printf("倒数第%d个节点值为：%d\n", k, slow->data);return 1;
}
//查找两个节点共同后缀的起始位置
Node* findIntersectionNode(Node *headA, Node *headB)
{if(headA == NULL || headB == NULL){return NULL;}Node *p = headA;int lenA = 0;int lenB = 0;//遍历链表A，获取链表A的长度while(p != NULL){p = p->next;lenA++;}//遍历链表B，获取链表B的长度p = headB;while(p != NULL){p = p->next;lenB++;}Node *m;//快指针Node *n;//慢指针int step;//两个单词之间数量的差值，可以用于快指针先走的步数if (lenA > lenB){step = lenA - lenB;m = headA;n = headB;}else{step = lenB - lenA;m = headB;n = headA;}//让快指针先走step步for (int i = 0; i < step; i++){m = m->next;}//快慢指针同步走，直到指向同一个节点退出循环while(m != n){m = m->next;n = n->next;}return m;
}int main(int argc, char const *argv[])
{Node *listA = initList();Node *listB = initList();Node *tailA = get_tail(listA);Node *tailB = get_tail(listB);tailA = insertTail(tailA, 'l');tailA = insertTail(tailA, 'o');tailA = insertTail(tailA, 'a');tailA = insertTail(tailA, 'd');tailB = insertTail(tailB, 'b');tailB = insertTail(tailB, 'e');Node *nodeI = initListWithElem('i');tailA = insertTailWithNode(tailA, nodeI);tailB = insertTailWithNode(tailB, nodeI);Node *nodeN = initListWithElem('n');tailA = insertTailWithNode(tailA, nodeN);tailB = insertTailWithNode(tailB, nodeN);Node *nodeG = initListWithElem('g');tailA = insertTailWithNode(tailA, nodeG);tailB = insertTailWithNode(tailB, nodeG);listNode(listA);listNode(listB);printf("%c\n",findIntersectionNode(listA,listB)->data);return 0;
}

        该代码思路就是通过数来控制数组下标，再通过该数组下标对应的数进行判断是否有重复的，可以进行除重使用
注：
        对于为什么使用指针接收或初始化数组，因为在堆区中申请空间使用malloc函数，其的使用方法是：
        (void*)malloc(申请的空间大小)，其返回的也是指针型的空间地址。
        所以应该使用指针去接收
        并且为了防止在之前的堆区数据未释放干净，使申请堆区内存时，申请失败
        则可以在申请后进行一次判断

if (p == NULL) 
{printf("内存分配失败\n");return;
}

                4、单链表--反转链表

                进行编写的图示经过

#include <stdio.h>
#include <stdlib.h>typedef int ElemType;typedef struct node{ElemType data;struct node *next;
}Node;//初化链表
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//初始化节点（带节点数据域参数）
Node* initListWithElem(ElemType e)
{Node *node = (Node*)malloc(sizeof(Node));node->data = e;node->next = NULL;return node;
}//头插法
int insertHead(Node* L, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//遍历
void listNode(Node* L)
{Node *p = L->next;while(p != NULL){printf("%d ", p->data);p = p->next;}printf("\n");
}//获取尾部结点
Node*  get_tail(Node  *L)
{Node *p = L;while(p->next != NULL){p = p->next;}return p;
}//尾插法
Node* insertTail(Node *tail, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;tail->next = p;p->next = NULL;return p;
}//尾插法（节点）
Node* insertTailWithNode(Node *tail, Node *node)
{tail->next = node;node->next = NULL;return node;
}//指定位置插入
int insertNode(Node *L, int pos, ElemType e)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}Node *q = (Node*)malloc(sizeof(Node));q->data = e;q->next = p->next;p->next = q;return 1;
}//删除节点
int deleteNode(Node *L, int pos)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}if(p->next == NULL){printf("要删除的位置错误\n");return 0;}Node *q = p->next;p->next = q->next;free(q);return 1;
}//获取链表长度
int listLength(Node *L)
{Node *p = L;int len = 0;while(p != NULL){p = p->next;len++;}return len;
}//释放链表
void freeList(Node *L)
{Node *p = L->next;Node *q;while(p != NULL){q = p->next;free(p);p = q;}L->next = NULL;
}//查找倒数第k个节点
int findNodeFS(Node *L, int k)
{Node *fast = L->next;Node *slow = L->next;for (int i = 0; i < k; i++){fast = fast->next;}while(fast != NULL){fast = fast->next;slow = slow->next;}printf("倒数第%d个节点值为：%d\n", k, slow->data);return 1;
}
//查找两个节点共同后缀的起始位置
Node* findIntersectionNode(Node *headA, Node *headB)
{if(headA == NULL || headB == NULL){return NULL;}Node *p = headA;int lenA = 0;int lenB = 0;while(p != NULL){p = p->next;lenA++;}p = headB;while(p != NULL){p = p->next;lenB++;}Node *m;Node *n;int step;if (lenA > lenB){step = lenA - lenB;m = headA;n = headB;}else{step = lenB - lenA;m = headB;n = headA;}for (int i = 0; i < step; i++){m = m->next;}while(m != n){m = m->next;n = n->next;}return m;
}//删除绝对值相同的节点
void removeNode(Node *L, int n)
{Node *p = L;int index;int *q = (int*)malloc(sizeof(int)*(n+1));for (int i = 0; i < n+1; i++){*(q + i) = 0;}while(p->next != NULL){index = abs(p->next->data);if(*(q+index) == 0){*(q + index) = 1;p = p->next;}else{Node *temp = p->next;p->next = temp->next;free(temp);}}free(q);
}//反转链表
Node* reverseList(Node* head)
{Node *first = NULL;Node *second = head->next;Node *third;while(second != NULL){third = second->next;second->next = first;first = second;second = third;}Node *hd = initList();hd->next = first;return hd;
}int main(int argc, char const *argv[])
{Node *list = initList();Node *tail = get_tail(list);tail = insertTail(tail, 1);tail = insertTail(tail, 2);tail = insertTail(tail, 3);tail = insertTail(tail, 4);tail = insertTail(tail, 5);tail = insertTail(tail, 6);listNode(list);Node* reverse = reverseList(list);listNode(reverse);return 0;
}


                5、单链表--删除中间节点


                        主要是利用快慢指针来进行寻找中间位置
                        针对奇数链表

#include <stdio.h>
#include <stdlib.h>typedef int ElemType;typedef struct node{ElemType data;struct node *next;
}Node;//初化链表
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//初始化节点（带节点数据域参数）
Node* initListWithElem(ElemType e)
{Node *node = (Node*)malloc(sizeof(Node));node->data = e;node->next = NULL;return node;
}//头插法
int insertHead(Node* L, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//遍历
void listNode(Node* L)
{Node *p = L->next;while(p != NULL){printf("%d ", p->data);p = p->next;}printf("\n");
}//获取尾部结点
Node*  get_tail(Node  *L)
{Node *p = L;while(p->next != NULL){p = p->next;}return p;
}//尾插法
Node* insertTail(Node *tail, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;tail->next = p;p->next = NULL;return p;
}//尾插法（节点）
Node* insertTailWithNode(Node *tail, Node *node)
{tail->next = node;node->next = NULL;return node;
}//指定位置插入
int insertNode(Node *L, int pos, ElemType e)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}Node *q = (Node*)malloc(sizeof(Node));q->data = e;q->next = p->next;p->next = q;return 1;
}//删除节点
int deleteNode(Node *L, int pos)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}if(p->next == NULL){printf("要删除的位置错误\n");return 0;}Node *q = p->next;p->next = q->next;free(q);return 1;
}//获取链表长度
int listLength(Node *L)
{Node *p = L;int len = 0;while(p != NULL){p = p->next;len++;}return len;
}//释放链表
void freeList(Node *L)
{Node *p = L->next;Node *q;while(p != NULL){q = p->next;free(p);p = q;}L->next = NULL;
}//查找倒数第k个节点
int findNodeFS(Node *L, int k)
{Node *fast = L->next;Node *slow = L->next;for (int i = 0; i < k; i++){fast = fast->next;}while(fast != NULL){fast = fast->next;slow = slow->next;}printf("倒数第%d个节点值为：%d\n", k, slow->data);return 1;
}
//查找两个节点共同后缀的起始位置
Node* findIntersectionNode(Node *headA, Node *headB)
{if(headA == NULL || headB == NULL){return NULL;}Node *p = headA;int lenA = 0;int lenB = 0;while(p != NULL){p = p->next;lenA++;}p = headB;while(p != NULL){p = p->next;lenB++;}Node *m;Node *n;int step;if (lenA > lenB){step = lenA - lenB;m = headA;n = headB;}else{step = lenB - lenA;m = headB;n = headA;}for (int i = 0; i < step; i++){m = m->next;}while(m != n){m = m->next;n = n->next;}return m;
}//删除绝对值相同的节点
void removeNode(Node *L, int n)
{Node *p = L;int index;int *q = (int*)malloc(sizeof(int)*(n+1));for (int i = 0; i < n+1; i++){*(q + i) = 0;}while(p->next != NULL){index = abs(p->next->data);if(*(q+index) == 0){*(q + index) = 1;p = p->next;}else{Node *temp = p->next;p->next = temp->next;free(temp);}}free(q);
}//反转链表
Node* reverseList(Node* head)
{Node *first = NULL;Node *second = head->next;Node *third;while(second != NULL){third = second->next;second->next = first;first = second;second = third;}Node *hd = initList();hd->next = first;return hd;
}//删除中间节点
int delMiddleNode(Node *head)
{Node *fast = head->next;Node *slow = head;while(fast != NULL && fast->next != NULL){fast = fast->next->next;slow = slow->next;}Node *q = slow->next;slow->next = q->next;free(q);return 1;
}int main(int argc, char const *argv[])
{Node *list = initList();Node *tail = get_tail(list);tail = insertTail(tail, 1);tail = insertTail(tail, 2);tail = insertTail(tail, 3);tail = insertTail(tail, 4);tail = insertTail(tail, 5);tail = insertTail(tail, 6);tail = insertTail(tail, 7);listNode(list);delMiddleNode(list);listNode(list);return 0;
}

                6、单链表--将链表:a,a1,a2.....an-2,an-1,an 变为a,an,a1,an-1,a2,an-2......


                        设计思路为：先找到中间的位置将其断开，然后将后半部分反转，再进行插空链接

                        成为这样纸

#include <stdio.h>
#include <stdlib.h>typedef int ElemType;typedef struct node{ElemType data;struct node *next;
}Node;//初化链表
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//初始化节点（带节点数据域参数）
Node* initListWithElem(ElemType e)
{Node *node = (Node*)malloc(sizeof(Node));node->data = e;node->next = NULL;return node;
}//头插法
int insertHead(Node* L, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//遍历
void listNode(Node* L)
{Node *p = L->next;while(p != NULL){printf("%d ", p->data);p = p->next;}printf("\n");
}//获取尾部结点
Node*  get_tail(Node  *L)
{Node *p = L;while(p->next != NULL){p = p->next;}return p;
}//尾插法
Node* insertTail(Node *tail, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;tail->next = p;p->next = NULL;return p;
}//尾插法（节点）
Node* insertTailWithNode(Node *tail, Node *node)
{tail->next = node;node->next = NULL;return node;
}//指定位置插入
int insertNode(Node *L, int pos, ElemType e)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}Node *q = (Node*)malloc(sizeof(Node));q->data = e;q->next = p->next;p->next = q;return 1;
}//删除节点
int deleteNode(Node *L, int pos)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}if(p->next == NULL){printf("要删除的位置错误\n");return 0;}Node *q = p->next;p->next = q->next;free(q);return 1;
}//获取链表长度
int listLength(Node *L)
{Node *p = L;int len = 0;while(p != NULL){p = p->next;len++;}return len;
}//释放链表
void freeList(Node *L)
{Node *p = L->next;Node *q;while(p != NULL){q = p->next;free(p);p = q;}L->next = NULL;
}//查找倒数第k个节点
int findNodeFS(Node *L, int k)
{Node *fast = L->next;Node *slow = L->next;for (int i = 0; i < k; i++){fast = fast->next;}while(fast != NULL){fast = fast->next;slow = slow->next;}printf("倒数第%d个节点值为：%d\n", k, slow->data);return 1;
}
//查找两个节点共同后缀的起始位置
Node* findIntersectionNode(Node *headA, Node *headB)
{if(headA == NULL || headB == NULL){return NULL;}Node *p = headA;int lenA = 0;int lenB = 0;while(p != NULL){p = p->next;lenA++;}p = headB;while(p != NULL){p = p->next;lenB++;}Node *m;Node *n;int step;if (lenA > lenB){step = lenA - lenB;m = headA;n = headB;}else{step = lenB - lenA;m = headB;n = headA;}for (int i = 0; i < step; i++){m = m->next;}while(m != n){m = m->next;n = n->next;}return m;
}//删除绝对值相同的节点
void removeNode(Node *L, int n)
{Node *p = L;int index;int *q = (int*)malloc(sizeof(int)*(n+1));for (int i = 0; i < n+1; i++){*(q + i) = 0;}while(p->next != NULL){index = abs(p->next->data);if(*(q+index) == 0){*(q + index) = 1;p = p->next;}else{Node *temp = p->next;p->next = temp->next;free(temp);}}free(q);
}//反转链表
Node* reverseList(Node* head)
{Node *first = NULL;Node *second = head->next;Node *third;while(second != NULL){third = second->next;second->next = first;first = second;second = third;}Node *hd = initList();hd->next = first;return hd;
}//删除中间节点
int delMiddleNode(Node *head)
{Node *fast = head->next;Node *slow = head;while(fast != NULL && fast->next != NULL){fast = fast->next->next;slow = slow->next;}Node *q = slow->next;slow->next = q->next;free(q);return 1;
}//链表重新排序
void reOrderList(Node *head)
{Node *fast = head->next;Node *slow = head;while(fast != NULL && fast->next != NULL){fast = fast->next->next;slow = slow->next;}Node *first = NULL;Node *second = slow->next;slow->next = NULL;Node *third = NULL;while(second != NULL){third = second->next;second->next = first;first = second;second = third;}Node *p1 = head->next;Node *q1 = first;Node *p2, *q2;while(p1 != NULL && q1 != NULL){p2 = p1->next;q2 = q1->next;p1->next = q1;q1->next = p2;p1 = p2;q1 = q2;}
}
int main(int argc, char const *argv[])
{Node *list = initList();Node *tail = get_tail(list);tail = insertTail(tail, 1);tail = insertTail(tail, 2);tail = insertTail(tail, 3);tail = insertTail(tail, 4);tail = insertTail(tail, 5);tail = insertTail(tail, 6);listNode(list);reOrderList(list);listNode(list);return 0;
}


                7、单链表--判断链表是否有环

                                就是利用快慢指针来看是否能追到，因为快慢，所以只要有环不论多少次都会追到，则可运用其来进行判断。

#include <stdio.h>
#include <stdlib.h>typedef int ElemType;typedef struct node{ElemType data;struct node *next;
}Node;//初化链表
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//初始化节点（带节点数据域参数）
Node* initListWithElem(ElemType e)
{Node *node = (Node*)malloc(sizeof(Node));node->data = e;node->next = NULL;return node;
}//头插法
int insertHead(Node* L, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//遍历
void listNode(Node* L)
{Node *p = L->next;while(p != NULL){printf("%d ", p->data);p = p->next;}printf("\n");
}//获取尾部结点
Node*  get_tail(Node  *L)
{Node *p = L;while(p->next != NULL){p = p->next;}return p;
}//尾插法
Node* insertTail(Node *tail, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;tail->next = p;p->next = NULL;return p;
}//尾插法（节点）
Node* insertTailWithNode(Node *tail, Node *node)
{tail->next = node;node->next = NULL;return node;
}//指定位置插入
int insertNode(Node *L, int pos, ElemType e)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}Node *q = (Node*)malloc(sizeof(Node));q->data = e;q->next = p->next;p->next = q;return 1;
}//删除节点
int deleteNode(Node *L, int pos)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}if(p->next == NULL){printf("要删除的位置错误\n");return 0;}Node *q = p->next;p->next = q->next;free(q);return 1;
}//获取链表长度
int listLength(Node *L)
{Node *p = L;int len = 0;while(p != NULL){p = p->next;len++;}return len;
}//释放链表
void freeList(Node *L)
{Node *p = L->next;Node *q;while(p != NULL){q = p->next;free(p);p = q;}L->next = NULL;
}//查找倒数第k个节点
int findNodeFS(Node *L, int k)
{Node *fast = L->next;Node *slow = L->next;for (int i = 0; i < k; i++){fast = fast->next;}while(fast != NULL){fast = fast->next;slow = slow->next;}printf("倒数第%d个节点值为：%d\n", k, slow->data);return 1;
}
//查找两个节点共同后缀的起始位置
Node* findIntersectionNode(Node *headA, Node *headB)
{if(headA == NULL || headB == NULL){return NULL;}Node *p = headA;int lenA = 0;int lenB = 0;while(p != NULL){p = p->next;lenA++;}p = headB;while(p != NULL){p = p->next;lenB++;}Node *m;Node *n;int step;if (lenA > lenB){step = lenA - lenB;m = headA;n = headB;}else{step = lenB - lenA;m = headB;n = headA;}for (int i = 0; i < step; i++){m = m->next;}while(m != n){m = m->next;n = n->next;}return m;
}//删除绝对值相同的节点
void removeNode(Node *L, int n)
{Node *p = L;int index;int *q = (int*)malloc(sizeof(int)*(n+1));for (int i = 0; i < n+1; i++){*(q + i) = 0;}while(p->next != NULL){index = abs(p->next->data);if(*(q+index) == 0){*(q + index) = 1;p = p->next;}else{Node *temp = p->next;p->next = temp->next;free(temp);}}free(q);
}//反转链表
Node* reverseList(Node* head)
{Node *first = NULL;Node *second = head->next;Node *third;while(second != NULL){third = second->next;second->next = first;first = second;second = third;}Node *hd = initList();hd->next = first;return hd;
}//删除中间节点
int delMiddleNode(Node *head)
{Node *fast = head->next;Node *slow = head;while(fast != NULL && fast->next != NULL){fast = fast->next->next;slow = slow->next;}Node *q = slow->next;slow->next = q->next;free(q);return 1;
}//链表重新排序
void reOrderList(Node *head)
{Node *fast = head;Node *slow = head;while(fast != NULL && fast->next != NULL){fast = fast->next->next;slow = slow->next;}Node *first = NULL;Node *second = slow->next;slow->next = NULL;Node *third = NULL;while(second !=NULL){third = second->next;second->next = first;first = second;second = third;}Node *p1 = head->next;Node *q1 = first;Node *p2, *q2;while(p1 != NULL && q1 != NULL){p2 = p1->next;q2 = q1->next;p1->next = q1;q1->next = p2;p1 = p2;q1 = q2;}
}//判断链表是否有环
int isCycle(Node *head)
{Node *fast = head;Node *slow = head;while(fast != NULL && fast->next != NULL){fast = fast->next->next;slow = slow->next;if (fast == slow){return 1;}}return 0;
}int main(int argc, char const *argv[])
{Node *list = initList();Node *tail = get_tail(list);tail = insertTail(tail, 1);tail = insertTail(tail, 2);tail = insertTail(tail, 3);Node *three = tail;tail = insertTail(tail, 4);tail = insertTail(tail, 5);tail = insertTail(tail, 6);tail = insertTail(tail, 7);tail = insertTail(tail, 8);tail->next = three;//listNode(list);if (isCycle(list)){printf("有环\n");}else{printf("无环\n");}return 0;
}

                8、单链表--判断链表有环的入口在哪


                        也可运用快慢指针，当第一次相遇后，让一个停止，另一个继续走，这时记录他们所走的次数，则可知道这个环中有几个节点，再让其快慢指针重新走，并让快指针先走这几步，再同步走，当相遇时，此节点则为入口节点

#include <stdio.h>
#include <stdlib.h>typedef int ElemType;typedef struct node{ElemType data;struct node *next;
}Node;//初化链表
Node* initList()
{Node *head = (Node*)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}//初始化节点（带节点数据域参数）
Node* initListWithElem(ElemType e)
{Node *node = (Node*)malloc(sizeof(Node));node->data = e;node->next = NULL;return node;
}//头插法
int insertHead(Node* L, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;p->next = L->next;L->next = p;return 1;
}//遍历
void listNode(Node* L)
{Node *p = L->next;while(p != NULL){printf("%d ", p->data);p = p->next;}printf("\n");
}//获取尾部结点
Node*  get_tail(Node  *L)
{Node *p = L;while(p->next != NULL){p = p->next;}return p;
}//尾插法
Node* insertTail(Node *tail, ElemType e)
{Node *p = (Node*)malloc(sizeof(Node));p->data = e;tail->next = p;p->next = NULL;return p;
}//尾插法（节点）
Node* insertTailWithNode(Node *tail, Node *node)
{tail->next = node;node->next = NULL;return node;
}//指定位置插入
int insertNode(Node *L, int pos, ElemType e)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}Node *q = (Node*)malloc(sizeof(Node));q->data = e;q->next = p->next;p->next = q;return 1;
}//删除节点
int deleteNode(Node *L, int pos)
{Node *p = L;int i = 0;while(i < pos-1){p = p->next;i++;if (p == NULL){return 0;}}if(p->next == NULL){printf("要删除的位置错误\n");return 0;}Node *q = p->next;p->next = q->next;free(q);return 1;
}//获取链表长度
int listLength(Node *L)
{Node *p = L;int len = 0;while(p != NULL){p = p->next;len++;}return len;
}//释放链表
void freeList(Node *L)
{Node *p = L->next;Node *q;while(p != NULL){q = p->next;free(p);p = q;}L->next = NULL;
}//查找倒数第k个节点
int findNodeFS(Node *L, int k)
{Node *fast = L->next;Node *slow = L->next;for (int i = 0; i < k; i++){fast = fast->next;}while(fast != NULL){fast = fast->next;slow = slow->next;}printf("倒数第%d个节点值为：%d\n", k, slow->data);return 1;
}
//查找两个节点共同后缀的起始位置
Node* findIntersectionNode(Node *headA, Node *headB)
{if(headA == NULL || headB == NULL){return NULL;}Node *p = headA;int lenA = 0;int lenB = 0;while(p != NULL){p = p->next;lenA++;}p = headB;while(p != NULL){p = p->next;lenB++;}Node *m;Node *n;int step;if (lenA > lenB){step = lenA - lenB;m = headA;n = headB;}else{step = lenB - lenA;m = headB;n = headA;}for (int i = 0; i < step; i++){m = m->next;}while(m != n){m = m->next;n = n->next;}return m;
}//删除绝对值相同的节点
void removeNode(Node *L, int n)
{Node *p = L;int index;int *q = (int*)malloc(sizeof(int)*(n+1));for (int i = 0; i < n+1; i++){*(q + i) = 0;}while(p->next != NULL){index = abs(p->next->data);if(*(q+index) == 0){*(q + index) = 1;p = p->next;}else{Node *temp = p->next;p->next = temp->next;free(temp);}}free(q);
}//反转链表
Node* reverseList(Node* head)
{Node *first = NULL;Node *second = head->next;Node *third;while(second != NULL){third = second->next;second->next = first;first = second;second = third;}Node *hd = initList();hd->next = first;return hd;
}//删除中间节点
int delMiddleNode(Node *head)
{Node *fast = head->next;Node *slow = head;while(fast != NULL && fast->next != NULL){fast = fast->next->next;slow = slow->next;}Node *q = slow->next;slow->next = q->next;free(q);return 1;
}//链表重新排序
void reOrderList(Node *head)
{Node *fast = head;Node *slow = head;while(fast != NULL && fast->next != NULL){fast = fast->next->next;slow = slow->next;}Node *first = NULL;Node *second = slow->next;slow->next = NULL;Node *third = NULL;while(second !=NULL){third = second->next;second->next = first;first = second;second = third;}Node *p1 = head->next;Node *q1 = first;Node *p2, *q2;while(p1 != NULL && q1 != NULL){p2 = p1->next;q2 = q1->next;p1->next = q1;q1->next = p2;p1 = p2;q1 = q2;}
}//判断链表是否有环
int isCycle(Node *head)
{Node *fast = head;Node *slow = head;while(fast != NULL && fast->next != NULL){fast = fast->next->next;slow = slow->next;if (fast == slow){return 1;}}return 0;
}//找到链表环的入口
Node* findBegin(Node *head)
{Node *fast = head;Node *slow = head;while(fast != NULL && fast->next != NULL){fast = fast->next->next;slow = slow->next;if (fast == slow){Node *p = fast;int count = 1;while(p->next != slow){count++;p = p->next;}fast = head;slow = head;for (int i = 0; i < count; i++){fast = fast->next;}while(fast != slow){fast = fast->next;slow = slow->next;}return slow;}}return NULL;
}
int main(int argc, char const *argv[])
{Node *list = initList();Node *tail = get_tail(list);tail = insertTail(tail, 1);tail = insertTail(tail, 2);tail = insertTail(tail, 3);Node *three = tail;tail = insertTail(tail, 4);tail = insertTail(tail, 5);tail = insertTail(tail, 6);tail = insertTail(tail, 7);tail = insertTail(tail, 8);tail->next = three;Node *p = findBegin(list);printf("%d\n", p->data);return 0;
}

        E、双向链表


                1、双向链表--初始化


                        比单链表多了一个指向前驱的指针

                

                2、双向链表--头插法

                                变为

                 3、双向链表--尾插法


                                与单链表相同需要通过遍历找到最后结点指针域是NULL的

Node* get_tail(Node  *L)
{Node  *p=L;while( p -> next !=  NULL){p = p -> next ;}return  p;
}


                        再进行尾插法

                4、双向链表--在指定位置插入数据


                        首先先找到所插入位置的前一个节点（利用遍历）

                        再进行插入：

                5、双向链表--删除节点


                        相同先通过遍历找到所删除节点的前驱位置，再进行操作

                        删除节点为将该节点前驱和后继进行相连，并将本节点申请的空间进行释放

        F、顺序表与链表的对比

结语

学习于B站的 逊哥带你学计算机 up主 的 《数据结构（C 语言描述）》也许是全站最良心最通俗易懂最好看的数据结构课（最迟每周五更新~~）

还在学习中，如有错误还请大佬们指出，有问题可相互交流

《数据结构（C 语言描述）》也许是全站最良心最通俗易懂最好看的数据结构课（最迟每周五更新~~）_哔哩哔哩_bilibili