一、链表的概念
概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链 接次序实现的 。
注：1、从上图中可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续。
2、从现实中的结点一般是通过malloc函数申请的，所以其内存分配是在堆区。
3、从堆上申请的空间，是按照一定的策略来分配的，则一个节点的大小为8个字节。
二、链表的分类
实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1. 单向或者双向链表
2. 带头或者不带头（是否有自带哨兵位头结点）
第二个链表的d1指向了我们的哨兵位头结点。
3. 循环或者非循环链表
4.无头单向非循环链表和带头双向循环链表
1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结 构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向 循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而 简单了。
三、链表的实现（代码和注释）
无头+单向+非循环链表增删查改实现
头文件：
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> //要求存储的数据从0开始，依次存储 //静态的顺序表 //问题：开小了，不够用，开大了，存在浪费。 //struct SeqList //{ // int a[N]; // int size;//记录存储了多少个数据。 //}; typedef int SLDateType;//宏定义我们的 SLDateType是int类型的 //动态的顺序表 typedef struct SeqList { SLDateType* a; int size; //存储数据个数 int capacity;//存储空间大小 }SL, SeqList; void SeqListPrint(SeqList* psl);//链表的打印 void SeqListInit(SeqList* psl);//链表的初始化 void SeqListDestroy(SeqList* psl);//链表的销毁 void SeqListCheckCapacity(SeqList* psl);//检查内存空间是否足够 //时间复杂度是o(1) void SeqListPushBack(SeqList* psl, SLDateType x);//链表的尾插 void SeqListPopBack(SeqList* psl);//链表的尾删 //时间复杂度是o(n) void SeqListPushFront(SeqList* psl, SLDateType x);//链表的头插 void SeqListPopFront(SeqList* psl);//链表的头删 void SeqListInsert(SeqList* psl, size_t pos, SLDateType x); // 删除pos位置的数据 void SeqListErase(SeqList* psl, size_t pos); // 顺序表查找 int SeqListFind(SeqList* psl, SLDateType x);
链表的函数实现部分的代码：
#include"SeqList.h" #include<assert.h> void SeqListPrint(SeqList* psl)//结构体指针传参 { for (int i = 0; i < psl->size; ++i) { printf("%d ", psl->a[i]); } printf("\n"); } void SeqListInit(SeqList* psl) { assert(psl);//断言psl不为空 psl->a = NULL;//a就相当于是链表的头 psl->size = 0; psl->capacity = 0; } void SeqListDestroy(SeqList* psl)//链表的删除 { assert(psl); free(psl->a);//free掉链表中a这个节点的位置 psl->a = NULL;//将a指向空 psl->capacity = psl->size = 0;//将链表的内存大小置为0 } void SeqListCheckCapacity(SeqList* psl)//检查链表的内存，如果不够就增容。 { assert(psl); if (psl->size == psl->capacity) { //capacity == 0,所以要先特判一下capacity 的值 size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;//初始节点数为4，如果内存现在为0就扩大一倍 SLDateType* tmp = realloc(psl->a, sizeof(SLDateType) * newCapacity);//申请空间 if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } else { psl->a = tmp; psl->capacity = newCapacity;//原来的空间变为新空间 } } } void SeqListPushBack(SeqList* psl, SLDateType x) { //如果满了，要扩容 if (psl->size == psl->capacity) { //capacity == 0,所以要先特判一下capacity 的值 size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2; SLDateType* tmp = realloc(psl->a, sizeof(SLDateType) * newCapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } else { psl->a = tmp; psl->capacity = newCapacity; } } psl->a[psl->size] = x; psl->size++; } void SeqListPopBack(SeqList* psl) { assert(psl); if (psl->size > 0) { psl->size--;//尾删就size--就好了 } } void SeqListPushFront(SeqList* psl, SLDateType x) { assert(psl); SeqListCheckCapacity(psl); int end = psl->size - 1; while (end >= 0)//所有的数据往后挪1位 { psl->a[end + 1] = psl->a[end]; --end; } psl->a[0] = x;//两种操作是等价的 psl->size++; //SeqListInsert(psl, 0, x);在头部插入。 } void SeqListPopFront(SeqList* psl) { assert(psl); if (psl->size > 0) { int begin = 1; while (psl->size > begin) { psl->a[begin - 1] = psl->a[begin]; ++begin; } --psl->size; } } void SeqListInsert(SeqList* psl, size_t pos, SLDateType x) { // 暴力检查 assert(psl); // 温和检查 if (pos > psl->size) { printf("pos 越界：%d\n", pos); return; //exit(-1); } // 暴力检查 //assert(pos <= psl->size); SeqListCheckCapacity(psl); //int end = psl->size - 1; //while (end >= (int)pos) //{ // psl->a[end + 1] = psl->a[end]; // --end; //} size_t end = psl->size; while (end > pos) { psl->a[end] = psl->a[end - 1]; --end; } psl->a[pos] = x; psl->size++; }
四、链表oj题（小试牛刀）
1、leetcode203移除链表元素力扣
包含三种情况
画个图分析：
思路：情况一和情况二都可以用prev和cur指针遍历数组的两个元素， if cur指针不等于6，prev指针和cur指针都往前走，如果cur = 6，prev跳到cur的下一个位置
如果是第三种情况，则需先找到head != val的位置，再重复进行如上操作。
代码示例：
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* prev = NULL; struct ListNode* cur = head; while(cur) { if(cur->val != val)//当cur这个位置的值不等于val时往下走 { prev = cur;//prev跳到cur位置 cur = cur->next;//cur指针继续往下走 } else { struct ListNode* next = cur->next;//定义一个新的指针 if(prev == NULL)//头删，head为空的状态 { free(cur); head = next;//继续往后面走 cur = next; } else { free(cur);//free掉cur这个节点 prev->next = next;//跳过了cur这个点 cur = next;//cur继续往后走 } } } return head; }
2、leetcode206反转链表力扣
思路1：反转指针方向
思路二：用三个指针， n1, n2, n3 分别存放NULL, head, head->next;
代码示例：
struct ListNode* reverseList(struct ListNode* head) { if(head == NULL) return NULL; struct ListNode* n1, *n2, *n3; n1 = NULL; n2 = head; n3 = n2->next;//n3的地址是n2的下一位 while(n2) { n2->next = n1;//n2 的下一位指向 n1;起到掉头的作用 n1 = n2; n2 = n3; if(n3) n3 = n3->next; } return n1; }
方法2：头插法
殊途同归。newhead 相当于之前的n1, cur = n2, next = n3;
struct ListNode* reverseList(struct ListNode* head) { struct ListNode* NewHead = NULL; struct ListNode* cur = head; while(cur) { struct ListNode* next = cur->next; //头插 cur->next = NewHead;//代表链表的指向方向。 NewHead = cur;//接着把地址传过来(更新) cur = next;//（更新） } return NewHead; }
3、leetcode 876链表的中间结点力扣
思路：快慢指针法
struct ListNode* middleNode(struct ListNode* head) { struct ListNode* slow, * fast; slow = fast = head;//刚开始slow和fast指针都指向头 while(fast && fast->next) //想的是结束的条件，写的是继续的条件 { slow = slow->next; fast = fast->next->next;//fast 每次走两步 } return slow; }
