顺序表和链表

线性表

线性表（linear list）是n 个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构。

常见的线性表：顺序表、链表、栈、队列、字符串…

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

顺序表

概念与结构

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

顺序表和数组的区别？

顺序表的底层结构是数组，对数组的封装，实现了常用的增、删、查、改等接口。

分类

静态顺序表

使用定长数组存储元素。

typedef int SLDatatype;#define N 7typedef struct SeqList
{SLDatatype a[N];	//定长数组int size;			//有效数据个数
}SL;

缺陷：

• 空间给少了不够用
• 空间给多了造成空间浪费

动态顺序表

typedef int SLDatatype;typedef struct SeqList
{SLDatatype* a;int size;		//有效数据个数int capacity;	//空间容量
}SL;

动态顺序表的实现

SeqList.c

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定义顺序表结构
typedef int SLDataType;typedef struct SeqList
{SLDataType* arr;int size;int capacity;
}SL;//初始化
void SLInit(SL* s);//销毁
void SLDesTory(SL* ps);//查找
int SLFind(SL* ps, SLDataType x);//打印
void SLPrint(SL s);//扩容
void SLCheckCapacity(SL* ps);//尾插
void SLPushBack(SL* ps, SLDataType x);//头插
void SLPushFront(SL* ps, SLDataType x);//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x);//尾删
void SLPopBack(SL* ps);//头删
void SLPopFront(SL* ps);//删除指定位置的数据
void SLErase(SL* ps, int pos);

SeqList.c

#include"SeqList.h"//初始化
void SLInit(SL* ps)
{/*传址调用,能够直接对顺序表的值进行修改*/ps->arr = NULL;ps->size = ps->capacity = 0;
}//销毁
void SLDesTory(SL* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}//查找
int SLFind(SL* ps, SLDataType x)
{/*找到了，返回下标没找到，返回-1*/assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x)return i;}return -1;
}//打印
void SLPrint(SL s)
{for (int i = 0; i < s.size; i++){printf("%d ", s.arr[i]);}
}//扩容
void SLCheckCapacity(SL* ps)
{/*可能存在的问题：1. capacity为02. 若每次增加的空间较小，可能导致频繁扩容，效率低下若每次开辟的空间较大，可能存在空间浪费-->扩容一般成倍数增加内存*/if (ps->size == ps->capacity)//空间满了{int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;SLDataType* tmp = (SLDataType*)realloc((void*)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[ps->size++] = x;
}//头插
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;
}//在指定位置之前插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{/*pos可以直接输入值，也可以为SLFind的返回值0 <= pos < size*/assert(ps);assert(pos >= 0 && pos < ps->size);SLCheckCapacity(ps);for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}//尾删
void SLPopBack(SL* ps)
{/*顺序表不能为空*/assert(ps && ps->size);ps->size--;/*不需要给ps->arr[size - 1]修改值ps->size--后，ps->arr[size - 1]的值并不会影响其他操作*/
}//头删
void SLPopFront(SL* ps)
{assert(ps && ps->size);for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}//删除指定位置的数据
void SLErase(SL* ps, int pos)
{assert(ps && ps->size);assert(pos >= 0 && pos < ps->size);for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

顺序表算法题

[移除元素](https://leetcode.cn/problems/remove-element/description/)

思路 1：另建临时数组（空间的复杂度为O(N)，且需要对numsSize = 0的请况另外做讨论，方法不好）。

思路 2：双指针法，创建两个变量指向数组。

int removeElement(int* nums, int numsSize, int val) 
{int src = 0;int dst = 0;//由dst直接记录不等于 val 的元素个数，不用额外创建变量//不用额外讨论 numsSize = 0 的请况。while (src < numsSize){//找出不等于 val 的元素个数if (nums[src] != val){nums[dst++] = nums[src];}src++;}return dst;
}

[删除有序数组中的重复项](https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/)

思路：双指针法，创建两个变量分别指向起始位置和下一个位置（便于判断是否为唯一元素）

上述代码可以进一步简化，省略对numsSize的分类讨论。

int removeDuplicates(int* nums, int numsSize)
{int dst = 0;int src = dst + 1;while (src < numsSize){if (nums[src] != nums[dst] && ++dst != src)//避免重复赋值{nums[dst] = nums[src];}src++;}return dst + 1;
}

[合并两个有序数组](https://leetcode.cn/problems/merge-sorted-array/description/)

思路 1：先合并，再进行冒泡排序（时间复杂度O(N^2)，方法不好）

思路 2：由于nums1的后n个元素为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 = m + n - 1;while (l1 >= 0 && l2 >= 0){nums1[l3--] = nums1[l1] > nums2[l2] ? nums1[l1--] : nums2[l2--];}while (l2 >= 0){nums1[l3--] = nums2[l2--];}//l1 >= 0的情况不需要操作
}

链表

概念与结构

链表是一种**物理结构上非连续、非顺序**的存储结构，数据元素的**逻辑顺序是通过链表中的指针链接次序实现**的。

结点

与顺序表不同，链表里的每一块区域都是独立申请下来的空间，我们称之为“结点/节点”。

结点的组成主要有两个部分：当前结点要保存的数据和下一个结点的地址（指针变量）。

链表中每个结点都是独立申请的（即需要插入数据时才去申请一块结点的空间），我们需要通过指针变量来保存下一个结点位置才能从当前结点找到下一个结点。

//定义结点结构
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;

链表的性质

1. 链式机构在逻辑上是连续的，在物理结构上不一定连续

2. 结点一般是从堆上申请的

3. 从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续

链表的分类

链表的结构非常多样，下列情况组合起来共有8种（2x2x2）链表结构：

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：无头单向非循环链表（单链表）和带头双向循环链表（双向链表）。

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子
   结构，如哈希桶、图的邻接表等等。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头
   双向循环链表。

单链表（singly-linked list)

注意：

在单链表中提到的头结点并不是“哨兵位”结点，而是指链表的第一个结点，这种表述是不规范的。

链表的打印

void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("\n");
}

单链表的实现

SList.h

#include<stdio.h>
#include<stdlib.h> 
#include<assert.h>//定义结点结构
typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//向操作系统申请一个新结点
SLTNode* SLTBuyNode(SLTDataType x);//销毁链表
void SLTDesTroy(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//打印
void SLTPrint(SLTNode* phead);//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x); //在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在指定位置之后插入数据
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);//尾删
void SLTPopBack(SLTNode** pphead);//头删
void SLTPopFront(SLTNode** pphead);//删除指定位置的结点
void SLTErase(SLTNode** pphead, SLTNode* pos);

SList.c

#include"SList.h"//向操作系统申请一个新结点
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}//销毁链表
void SLTDesTroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur = phead;while (pcur){if (pcur->data == x)return pcur;pcur = pcur->next;}return NULL;
}//打印链表
void SLTPrint(SLTNode* phead)
{/*定义pcur，避免后续需要使用首结点而找不到的情况*/SLTNode* pcur = phead;while (pcur){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("NULL\n");
}//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{/*需要对plist做出修改，采用传址调用*/assert(pphead);SLTNode* newnode = SLTBuyNode(x);//链表为空，phead直接指向newnodeif (*pphead == NULL)*pphead = newnode;//链表不为空，寻找尾结点else{SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}ptail->next = newnode;}
}//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && pos);//pos就是头结点if (*pphead == pos){//头插SLTPushFront(pphead, x);}else{SLTNode* newnode = SLTBuyNode(x);//pos在头结点之后-->找pos的前驱结点SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = newnode;newnode->next = pos;}
}//在指定位置之后插入数据
void SLTInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}//尾删
void SLTPopBack(SLTNode** pphead)
{/*链表不为空*/assert(pphead && *pphead);//只有一个结点的情况，直接释放，避免后续在prev为NULL时对其解引用if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//双指针，使得尾结点前驱结点next指针置为NULL，并释放尾结点SLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}
}//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}//删除指定位置的结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead && pos);//pos就是头结点if (*pphead == pos){//头删SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}//删除指定位置后的结点
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

单链表算法题

[移除链表元素](https://leetcode.cn/problems/remove-linked-list-elements/description/)

思路一：查找值为val的结点并返回结点位置，删除指定位置的结点（时间复杂度：O(N<sup>2</sup>)）

思路二：创建新链表，将值不为val的结点尾插到新链表中

typedef struct ListNode ListNode;ListNode* removeElements(ListNode* head, int val) 
{//创建新链表的头结点与尾结点ListNode* newhead = NULL;ListNode* newtail = NULL;ListNode* pcur = head;while (pcur){if (pcur->val != val){//新链表为空if (newhead == NULL)newhead = newtail = pcur;//新链表不为空else{//尾插newtail->next = pcur;newtail = pcur;}}pcur = pcur->next;}//使尾结点的next为空if (newtail)newtail->next = NULL;return newhead;
}

[反转链表](https://leetcode.cn/problems/reverse-linked-list/description/)

思路 1：创建新链表，将原链表的每个结点依次头插到新链表。

typedef struct ListNode ListNode;
ListNode* reverseList(ListNode* head) 
{ListNode* newhead = NULL;ListNode* newtail = NULL;ListNode* pcur = head;//头插while (pcur){//新链表为空if (newhead == NULL){newhead = newtail = pcur;pcur = pcur->next;}//新链表不为空else{ListNode* next = pcur->next;pcur->next = newhead;newhead = pcur;pcur = next;}  }//使尾结点的next为空if (newtail)newtail->next = NULL;return newhead;
}

思路二：创建三个指针，在原链表上修改指针的指向

typedef struct ListNode ListNode;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;
}

[链表的中间结点](https://leetcode.cn/problems/middle-of-the-linked-list/description/)

思路 1：第一次循环：遍历链表，求链表总长度，计算中间结点的位置

第二次循环：根据中间结点的位置走到中间结点

思路 2：快慢指针：慢指针每次走一步，快指针每次走两步。快指针的路程是慢指针的两倍。

typedef struct ListNode ListNode;ListNode* middleNode(ListNode* head) 
{ListNode* fast = head;ListNode* slow = head;/*注意：不能修改为fast->next && fast逻辑运算符的短路*/while (fast && fast->next){fast = fast->next->next;slow = slow->next;}return slow;
}

[合并两个有序链表](https://leetcode.cn/problems/merge-two-sorted-lists/description/)

思路 ：创建新链表，遍历原链表，比较大小，将小的结点尾插到新链表。

typedef struct ListNode ListNode;ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
{//处理链表为空的情况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)){//尾插l1if (newhead == NULL){newhead = newtail = l1;}else{newtail->next = l1;newtail = newtail->next;}l1 = l1->next;}else{//尾插l2if (newhead == NULL){newhead = newtail = l2;}else{newtail->next = l2;newtail = newtail->next;}l2 = l2->next;}}if (l1)newtail->next = l1;if (l2)newtail->next = l2;return newhead;
}

注意：上述代码的尾插部分由于对新链表分空与非空的情况而非常冗余，因此可以在创建的新链表的头结点添加一个“哨兵位”来简化代码。

typedef struct ListNode ListNode;ListNode* mergeTwoLists(ListNode* list1, 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)){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;return newhead->next;
}

[链表分割](https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70)

思路：创建大小两个链表，小链表存放<x的值，大链表存放>=x的值。再将两个链表相连。

typedef struct ListNode ListNode;ListNode* partition(ListNode* pHead, int x) 
{//创建两个非空链表ListNode* lesshead, *lesstail;ListNode* greaterhead, *greatertail;lesshead = lesstail = (ListNode*)malloc(sizeof(ListNode));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;}//大小链表首尾相连lesstail->next = greaterhead->next;//将大链表的尾结点的next指针置为NULLgreatertail->next = NULL;//释放空间ListNode* ret = lesshead->next;free(lesshead);free(greaterhead);lesshead = greaterhead = NULL;return ret;
}

[链表的回文结构](https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa)

思路 1：创建新链表保存原链表节点，翻转新链表，遍历两个链表比较结点是否相同（不符合额外空间复杂度为O(1)。

思路 2（投机取巧法）：由于保证链表长度小于等于 900，创建大小为 900 的数组，遍历原链表将结点的值依次存储在数组中

typedef struct ListNode ListNode;bool chkPalindrome(ListNode* A) 
{int i = 0;int arr[900] = { 0 };ListNode* pcur = A;//遍历原链表，将结点的值存储在数组中while (pcur){arr[i++] = pcur->val;pcur = pcur->next;}//判断数组是否为回文结构int left = 0, right = i - 1;while (left < right){if (arr[left] != arr[right])return false;right--;left++;}return true;
}

思路 3：找链表的中间结点，以链表的中间结点为新链表的头结点反转链表，将新链表与原链表比较。

typedef struct ListNode ListNode;//找中间节点
ListNode* middleNode(ListNode* head)
{ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){fast = fast->next->next;slow = slow->next;}return slow;
}//反转链表
ListNode* reverseList(ListNode* head)
{if (head == NULL)return head;ListNode* n1 = NULL, *n2 = head, *n3 = head->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;
}//判断回文结构
bool chkPalindrome(ListNode* A) 
{ListNode* mid = middleNode(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;
}

[相交链表](https://leetcode.cn/problems/intersection-of-two-linked-lists/description/)

思路：求两个链表长度，长链表先走长度差步，长短链表开始遍历比较结点的地址是否相同

typedef struct ListNode ListNode;ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
{ListNode* pa = headA;ListNode* pb = headB;int sizeA = 0;int sizeB = 0;while (pa){sizeA++;pa = pa->next;}while (pb){sizeB++;pb = pb->next;}int gap = abs(sizeA - sizeB);ListNode* shortlist = headA;ListNode* longlist = headB;if (sizeA > sizeB){shortlist = headB;longlist = headA;}while (gap--){longlist = longlist->next;}while (longlist){if (longlist == shortlist)return longlist;longlist = longlist->next;shortlist = shortlist->next;}return NULL;
}

[环形链表 I](https://leetcode.cn/problems/linked-list-cycle/description/)

思路：快慢指针在链表中追逐，若链表有环，则快慢指针会再次相遇。

证明：快慢指针一定会相遇。

若slow入环时fast与slow间的距离为N：

1. 快指针每次走两步，慢指针每次走一步，快慢指针最终会相遇：

在追逐过程中，fast与slow的距离变化：

typedef struct ListNode ListNode;bool hasCycle(ListNode *head) 
{//快慢指针ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){fast = fast->next->next;slow = slow->next;//相遇if (fast == slow)return true;}return false;
}

2. 快指针每次走三步，慢指针每次走一步，快慢指针最终会相遇：
   1. 距离的变化

在追逐过程中，fast与slow的距离变化：

结论：

    1. 如果N是偶数，第一轮就追上了2. 如果 N是奇数 ，第一轮追不上，快追上，错过了，距离变成`-1`，即`C-1`，进入新的一轮追击 1. `C-1`如果是偶数，那么下一轮就追上了2. `C-1`如果是奇数， 那么就永远都追不上 

总结⼀下追不上的前提条件：N是奇数，C是偶数

2. 路程

由于慢指针走一步，快指针要走三步，因此得出：3 * 慢指针路程 = 快指针路程

$ 3L=L +xC+C-N $

即：$ 2L=(x+1)C+N $

对上述公式继续分析：由于偶数乘以任何数都为偶数，因此2L一定为偶数，则可推导出可能得情况：

    * 情况 1：偶数 = 偶数 + 偶数* 情况 2：偶数 = 奇数 + 奇数

由 a 中的 i 得出的结论，如果N是偶数，则第一圈快慢指针就相遇了。

由 a 中的 ii 得出的结论， 如果N是奇数，则fast指针和slow指针在第一轮的时候套圈了，开始进 行下一轮的追逐；当N是奇数，要满足以上的公式，则(x+1)C必须也要为奇数，即C为奇数，满足 中的结论，则快慢指针会相遇

结论：

a 中的N是奇数，C是偶数的情况不成立，即快指针每次走三步，慢指针每次走一步的情况下，快慢指针最终也会相遇。

typedef struct ListNode ListNode;bool hasCycle(struct ListNode *head) 
{ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){slow = slow->next;//快指针每次走3步int n = 3;while (n--){if (fast->next)fast = fast->next;elsereturn false;}if (fast == slow)return true;}return false;
}

综上：快指针不论走多少步都可以满足在带环链表中相遇 。

[环形链表 II](https://leetcode.cn/problems/linked-list-cycle-ii/description/)

思路 1：建立数组存储地址，当地址与之前已经存储的地址相同时，结束循环。

思路 2：快慢指针在环中一定会相遇。相遇点到入环的起始结点的距离等于头结点到入环的起始结点的距离（注意顺序）

证明：快慢指针的相遇点和头结点到入环的起始结点的距离相同。

说明：

H为链表的起始点

E为环入口点

M 为快慢指针相遇点

假设：

环的长度为 R

H到E的距离为 L

E到M的距离为 X

M到E的距离为 R - X

路程：

slow = L + X

fast = L + X + nR

$fast = 2 * slow

即： L + X = nR

即： L = (n-1)R + R-X

因此一个指针从链表起始位置运行，一个指针从相遇点位置绕环，每次都走一步，两个指针最终会在环的入口点的位置相遇 。

typedef struct ListNode ListNode;ListNode *detectCycle(ListNode *head) 
{ListNode* slow = head;ListNode* fast = head;while (fast && fast->next){//找相遇点fast = fast->next->next;slow = slow->next;if (slow == fast){ListNode* pcur = head;//从相遇点和头结点开始向后遍历链表，结点相同就是入环起始结点while (pcur != slow){pcur = pcur->next;slow = slow->next;}return pcur;}}return NULL;
}

双向链表

实现双向链表

List.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定义结点结构
typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}LTNode;//向操作系统申请一个新结点
LTNode* LTBuyNode(LTDataType x);//链表的初始化
LTNode* LTInit();//链表的销毁
void LTDestory(LTNode* phead);//链表的打印
void LTPrint(LTNode* phead);//判断链表为空
bool LTEmpty(LTNode* phead);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//尾插
void LTPushBack(LTNode* phead, LTDataType x);//头插
void LTPushFront(LTNode* phead, LTDataType x);//尾删
void LTPopBack(LTNode* phead);//头删
void LTPopFront(LTNode* phead);//在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);//删除指定位置的结点
void LTErase(LTNode* pos);

List.c

#include"List.h"//向操作系统申请一个新结点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc");exit(1);}node->data = x;node->next = node->prev = node;return node;
}//链表的初始化
LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}
/*
写法二：
void LTInit(LTNode** pphead)
{*pphead = LTBuyNode(-1);
}
*///链表的销毁
/*
写法一
*/
void LTDestory(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;LTNode* next = NULL;while (pcur != phead){next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}/*
写法二：
void LTDestory(LTNode** pphead)
{assert(pphead && *pphead);LTNode* pcur = (*pphead)->next;LTNode* next = NULL;while (pcur != *pphead){next = pcur->next;free(pcur);pcur = next;}free(*pphead);*pphead = NULL;
}
此处为了保持链表接口一致性，建议都传递一级指针，后续手动将实参置为NULL
*///链表的打印
void LTPrint(LTNode* phead)
{/*双向指针为空的情况下是只有一个哨兵位*/LTNode* pcur = phead->next;while (pcur != phead){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("\n");
}//判断链表为空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x)return pcur;pcur = pcur->next;}return NULL;
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{/*由于指向哨兵位的指针不会发生变化，不需要传址调用*/assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead;newnode->prev = phead->prev;phead->prev->next = newnode;phead->prev = newnode;
}//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);newnode->next = phead->next;newnode->prev = phead;/*此处修改的先后顺序不能换*/phead->next->prev = newnode;phead->next = newnode;
}//尾删
void LTPopBack(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}//头删
void LTPopFront(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}//在指定位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);newnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}//删除指定位置的结点
void LTErase(LTNode* pos)
{assert(pos);pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

顺序表与链表的分析

不同点：	顺序表	链表（单链表）
存储空间	物理上一定连续	逻辑上连续，物理上不一定连续
随机访问	O(1)	O(N)
任意位置插入或删除数据	尾部：O(1) 头部/中间位置：O(N)	在指定位置之后：O(1) 在指定位置之前：O(N)
增加数据	空间不够时需要扩容，可能造成空间浪费	没有容量的概念，按需申请释放，不存在空间浪费
应用场景	元素高效存储+频繁访问	任意位置高效插入和删除