线性结构特点存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个“的数据元素除第一个以外的元素都只有一个前驱除最后一个元素以后的数据元素都有一个后继线性结构的两种形式顺序表顺序表是采用连续的内存空间存储线性表的数据元素一般用数组实现。随机访问可以通过下标直接访问任意元素时间复杂度O1插入、删除操作需要移动大量元素时间复杂度On容量固定静态顺序表或动态扩容动态顺序表会存在一定冗余空间链表链表采用不连续的内存空间存放数据元素每个结点包含数据域存放数据指针域存放下一个结点地址相邻元素物理地址不一定相邻依靠指针维系逻辑关系。上述图中就是一个单链表结点数据域next指针域如果有头指针头指针指向链表第一个结点尾结点指向NULL。链表的增删需要改指针指向增加结点需要开辟新的空间存储时间复杂度为O1访问链表中结点就需要遍历整个链表时间复杂度就为On。创建链表struct ListNode{ int val; //数据域struct ListNode* next;// 指针域};数组和链表的区别特性数组单链表内存连续离散随机访问O(1)O(n)中间插入删除O(n)找到结点后 O (1)内存开销小大存指针扩容需要拷贝动态分配补充双向链表多一个前驱指针删除效率更高删除效率更高但内存开销更大。链表的基本操作删除链表中数据为判断值为val的结点#include stdio.h #include stdlib.h //为malloc使用引入头文件 struct ListNode { int val; struct ListNode *next; //指向下一个节点的指针 }; struct ListNode*removeelement(struct ListNode*head,int val) {//将排查节点初始化为头节点并引入判断值val struct ListNode* dummy (struct ListNode*)malloc(sizeof(struct ListNode)); //创建虚拟头结点malloc申请堆内存空间并返回 dummy-nexthead;//虚拟节点连接原链表头部 struct ListNode*current dummy; //current从虚拟头结点开始遍历用来寻找待删除节点的前驱 while(current-next!NULL) { //当前节点后继不为空就继续查找 if(current-next-valval) {//判断后继节点的值是否为val(想要删除的节点) struct ListNode*temp current-next;//临时保存待删除节点 current-next current-next-next;//跳过待删除节点将该节点从链表中摘除 free(temp);//释放被删除节点的内存 }else { currentcurrent-next;//后继节点不满足删除条件且也不为空就可以移动到下一位 } } struct ListNode *newHead dummy-next;//保存处理完成后创建链表真正的头节点 free(dummy);//释放虚拟头节点内存 return newHead; } //创建个主程序来测试删除节点的程序可行性 struct ListNode* createNode(int v) { struct ListNode*pmalloc(sizeof(struct ListNode)); p-valv; p-nextNULL; return p; } //遍历打印链表所有元素 void printList(struct ListNode*h) { while(h) { printf(%d,h-val); hh-next; } printf(\n); } int main() { struct ListNode* head createNode(1); head-next createNode(2); head-next-nextcreateNode(6); head-next-next-nextcreateNode(3); head-next-next-next-nextcreateNode(6); headremoveelement(head,6); printList(head); return 0; }虚拟头结点的作用当删除/插入位置是链表第一个元素时不用单独修改head指针比如要删除值为1而1正好就是链表第一个结点即头结点如果不采用虚拟头结点要单独写ifhead-valval) ,再令headhead-next. 删除中间结点需要找前驱结点。头结点和普通结点的删除需要些if分支容易出错。相比之下使用虚拟头结点dummy之后不管要删的是真正头结点中间结点尾结点全都是找前驱结点current删除current-next。删除操作逻辑都一样不需要单独处理头结点的特殊情况。返回链表的中间结点核心逻辑定义快慢指针快指针每次走两步慢指针每次走一步。当快指针遍历完链表时慢指针走到中间结点。需要注意的是当链表为奇数时慢指针走到正中间结点为偶数时走到的是第二个中间结点#include stdio.h #include stdlib.h struct ListNode { int val; struct ListNode* next; }; struct ListNode* findMiddle(struct ListNode* head) { struct ListNode* slow head; struct ListNode* fast head; // Traverse the list with slow and fast pointers while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } return slow; }链表逆序三指针做法性能最高核心思想定义三个指针分别为从头结点开始遍历的current结点current的前驱precurrent的后继next。先利用next保存current后继结点防止断链current从本来指向next转为指向pre完成逆序过程。#include stdio.h #include stdlib.h struct ListNode { int val; struct ListNode* next; }; struct ListNode* reverseList(struct ListNode* head) { struct ListNode* prev NULL; struct ListNode* current head; struct ListNode* next NULL; while (current ! NULL) { next current-next; // Save the next node current-next prev; // Reverse the current nodes pointer prev current; // Move prev and current one step forward current next; } return prev; // prev will be the new head of the reversed list }链表排序:核心思想将链表截断为两个链表头结点与头结点下一个结点视作已排序部分,则此时从链表的下下一个结点开始视作未排序链表的头结点。分别定义三个指针一个指向已排序链表的头结点遍历有序部分查找插入结点的位置无序链表中定义两个指针一个用于指向无序链表头结点进行遍历另一个指针在进行与有序表结点数据比较后储存结点位置与有序链表相应位置相连接。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; void SortlinkList(Node *head) { if (head-next NULL) // head头结点head-next是已排序部分第一个结点 return; Node *tmp head-next-next; // 待处理第一个结点保存第二个链表头的位置 head-next-next NULL; // 截断链表 Node *p NULL; // 用于未排序链表保存要头插的节点 Node *h NULL; // 用来遍历第一个链表找插入位置的指针 while (tmp ! NULL) { p tmp; tmp tmp-next; for (h head; h-next ! NULL h-next-data p-data; h h-next) { } // 循环体空只移动h找位置 p-next h-next; // 找到h位置把p插入h后面 h-next p; } } Node *createNode(int val) { Node *n (Node *)malloc(sizeof(Node)); n-data val; n-next NULL; return n; } void printlist(Node *h) { Node *p h-next; while (p) { printf(%d, p-data); p p-next; } printf(\n); } int main() { Node *h createNode(-1); h-next createNode(1); h-next-next createNode(2); h-next-next-next createNode(6); h-next-next-next-next createNode(3); h-next-next-next-next-next createNode(6); h-next-next-next-next-next-next createNode(6); SortlinkList(h); printlist(h); return 0; }判断链表是否成环成环核心思路利用快慢指针如果一个链表成环快指针一定会在先出发的情况下追上满指针追及问题#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; int IsLoop(Node *head) { if (head NULL || head-next NULL) { return 0; } Node *fast head; Node *slow head; while (fast NULL || fast-next NULL) { slow slow-next; fast fast-next-next; if (slow fast) { return 1; } } return 0; }合并有序链表核心思路需要明确的是链表合并要考虑的因素。首先链表合并之后只会有一个头结点所以要手动去掉一个头结点分别比较两个链表数据域大小将找到的结点插到已排序链表之后。此外两个链表的长度不一定相等因此需要做判断当一个链表中结点已经被排完就应该直接接到下一个链表。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; Node *createList(int arr[], int n) { Node *head (Node *)malloc(sizeof(Node)); head-next NULL; Node *tail head; for (int i 0; i n; i) { Node *newNode (Node *)malloc(sizeof(Node)); newNode-data arr[i]; newNode-next NULL; tail-next newNode; tail newNode; } return head; } Node *combinelist(Node *head1, Node *head2) { if (head1 NULL) { return head2; } if (head2 NULL) { return head1; } Node *p1 head1-next; Node *p2 head2-next; Node *temp head1; free(head2); while (p1 ! NULL p2 ! NULL) { if (p1-data p2-data) { temp-next p2; p2 p2-next; temp temp-next; } else { temp-next p1; p1 p1-next; temp temp-next; } } if (p1 ! NULL) temp-next p1; else temp-next p2; return head1; } void printlist(Node *head) { Node *p head-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } int main(void) { int b[] {1, 3, 5, 7,9,11}; int a[] {2,4,6,8}; Node *L1 createList(b, 6); Node *L2 createList(a, 4); Node *res combinelist(L1, L2); printlist(res); return 0; }