目录一、数据结构基础概念1. 逻辑结构数据之间的逻辑关系2. 存储结构数据在计算机中的存储方式3. 算法与复杂度二、链表的核心概念1. 链表相关术语2. 链表 vs 数组三、单链表的基本操作C语言实现1. 节点结构定义2. 创建空链表3. 插入操作4. 查找与修改5. 删除操作6. 遍历打印三、单链表的进阶操作1. 找到链表的中间节点快慢指针2. 找到链表的倒数第k个节点双指针3. 判断链表是否有环快慢指针4. 链表的逆序反转一、数据结构基础概念数据结构主要研究数据与数据之间的关系。它分为两个层次1. 逻辑结构数据之间的逻辑关系线性结构一对一。如线性表、栈、队列。树形结构一对多。如树、二叉树。图形结构多对多。如网、图。集合无关系仅仅属于同一个集合。2. 存储结构数据在计算机中的存储方式顺序存储一段连续的空间用数组实现。逻辑相邻物理也相邻。链式存储空间不连续通过指针地址链接。逻辑相邻物理不一定相邻。索引存储建立附加的索引表。散列存储根据关键字计算存储地址哈希表。3. 算法与复杂度算法是对特定问题求解步骤的描述有五个特性有穷性、确定性、可行性、输入、输出。衡量算法好坏的核心指标是时间复杂度和空间复杂度常用大O表示法。例如顺序存储数组随机访问 O(1) O(1)插入/删除 O(n) O(n)。链式存储链表随机访问 O(n) O(n)插入/删除 O(1) O(1)。二、链表的核心概念链表是一种动态地进行存储分配的结构。它不需要预先分配固定大小的空间而是根据需要动态申请。1. 链表相关术语头指针head指向链表中第一个结点的指针是链表的入口。头节点第一个结点前附加的一个结点数据域通常不存放有效数据可放链表长度等指针域指向首节点。引入头节点可以简化插入和删除第一个结点的操作。首节点链表中第一个有效结点。尾节点最后一个结点其指针域为NULL。2. 链表 vs 数组对比项数组顺序存储链表链式存储内存空间连续不连续动态分配随机访问支持下标不支持需遍历插入/删除效率低需移动元素效率高只需改指针空间大小固定动态变化三、单链表的基本操作C语言实现我们以带头节点的单链表为例。1. 节点结构定义typedef struct node { int data; // 数据域 struct node *next; // 指针域 } node_t;2. 创建空链表node_t *linklist_creat(void){ node_t *head malloc(sizeof(node_t)); if(head NULL){ printf(linklist malloc failed); return NULL; } head-next NULL; return head; }3. 插入操作头插法新节点插在头节点之后。常用于链表逆序。尾插法新节点插在尾部。常用于保持插入顺序。//头插 void linklist_insert_head(node_t *phead,data_t data){ if(phead NULL){ printf(head NULL\n); return ; } //创建新节点 node_t *pnew malloc(sizeof(node_t)); if(pnew NULL){ printf(new linklist malloc failed\n); return ; } pnew -data data; //插入 pnew-next phead-next; phead-next pnew; } //尾插 void linklist_insert_rail(node_t *phead,data_t data){ if(phead NULL){ return; } node_t *pnew malloc(sizeof(node_t)); if(pnew NULL){ printf(new linklist malloc failed\n); return ; } node_t *p phead-next; pnew-data data; while(p-next!NULL){ p p-next; } p-next pnew; pnew-next NULL; }4. 查找与修改//查找 node_t *linklist_find_key(node_t *phead,data_t key){ if(phead NULL||is_empty(phead) ){ printf(phead is empty\n); return NULL; } node_t *p phead-next; while(p!NULL){ if(p-data key){ return p; } p p-next; } return NULL; } //修改先找再改 node_t *linklist_update(node_t *phead,data_t old,data_t new){ if(phead NULL||is_empty(phead) ){ printf(phead is empty\n); return NULL; } node_t *p linklist_find_key(phead,old); if(p NULL){ printf(not found %d\n,old); return NULL; } p-data new; return p; }5. 删除操作//从头开始删 void linklist_delete_head(node_t *phead){ if(phead NULL){ printf(head NULL\n); return ; } if(is_empty(phead) 1 ){ printf(phead is empty\n); return ; } node_t *pphead-next; phead-next p-next; free(p); p NULL; } //从结尾开始删 void linklist_delete_tail(node_t *phead){ if(phead NULL){ printf(head NULL\n); return ; } if(is_empty(phead) 1 ){ printf(phead is empty\n); return ; } node_t *pphead; //找尾节点的前一个节点 while(p-next-next!NULL){ p p-next; } free(p-next);//释放当前节点的下一个节点 p-next NULL;//当前节点的地址域设为空 } //删除指定值 void linklist_delete_key(node_t *phead,data_t key){ node_t *q linklist_find_key(phead,key); if(q NULL){ printf(not found\n); return ; } node_t *p phead; while(p-next ! q){ p p-next; } p-next q-next; free(q); q NULL; }6. 遍历打印//遍历打印链表 void linklist_print(node_t *phead){ //判断phead是否为空 //判断是否为空链表 if(phead NULL||is_empty(phead) ){ printf(phead is empty\n); return; } //遍历 node_t *p phead-next; while(p ! NULL){ printf(%d ,p-data); p p-next; } putchar(\n); }三、单链表的进阶操作1. 找到链表的中间节点快慢指针思路快指针一次走两步慢指针一次走一步。快指针走到尾时慢指针正好在中间。node_t *linklist_find_mid(node_t *phead){ if(phead NULL || is_empty(phead) 1){ printf(mid find fail\n); return NULL; } node_t *p phead; node_t *q phead; while(p!NULL p-next!NULL){ p p-next-next; q q-next; } return q; }2. 找到链表的倒数第k个节点双指针思路先让快指针走k步然后快慢指针同时走。快指针走到NULL时慢指针正好在倒数第k个位置。//找倒数第k个值的位置双指针 node_t *linklist_find_behind_key(node_t *phead,int k){ if(pheadNULL||is_empty(phead)){ printf(find fail\n); return NULL; } node_t *p phead; node_t *q phead; while(k){ if(p-next NULL){ printf(have no enough node\n); return NULL; } p p-next; --k; } while(p!NULL){ p p-next; q q-next; } return q; }3. 判断链表是否有环快慢指针思路快指针一次走两步慢指针一次走一步。如果链表有环快慢指针必定相遇。//是否含有环快慢指针 int linklist_is_cirlc(node_t *phead){ if(phead NULL ||is_empty(phead) 1){ return -1; } node_t *p phead; node_t *q phead; while(p!NULL p-next !NULL){ p p-next-next; q q-next; if(pq){ return 1; } } return 0; }4. 链表的逆序反转思路1使用头插法。遍历原链表依次将每个节点插入到新链表的头部。//链表逆序双指针 void linklist_reverse(node_t *phead){ if(phead NULL || is_empty(phead) 1){ return ; } node_t *p phead-next; node_t *q p-next; if(q NULL){ return ; } phead-next NULL; while(p!NULL){ q p-next; p-next phead-next; phead-next p; p q; } }思路2使用三个指针prev、curr、next遍历链表逐个将当前节点的next指针反转最终让头节点指向新的首节点原来的尾节点。//链表逆序三指针 void linklist_reverse_plus(node_t *phead){ if(phead NULL || is_empty(phead) 1){ return ; } node_t *prev NULL; node_t *curr phead-next; if(curr-next NULL){ return ; } while(curr!NULL){ node_t *next curr-next; curr-next prev; prev curr; curr next; } phead-next prev; }对比项思路一头插法思路二三指针法核心操作从原链表取节点头插到新链表直接反转每个节点的 next 指针指针数量2~3 个p, q, head-next3 个prev, curr, next代码直观性较直观但需要理解头插过程更直观直接反映“反转”动作是否改变头节点不改变头节点只改变 head-next不改变头节点只改变 head-next