3. 单链表

3. 单链表文章目录3. 单链表3.1 概念与结构3.1.1 结点3.1.2 链表的性质3.1.3 链表的打印3.2 实现单链表3.3链表的分类3.4单链表算法题3.4.23.4.2移除链表元素3.4.3反转链表3.4.4 链表的中间结点3.1 概念与结构概念链表是⼀种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的淡季时⻋次的⻋厢会相应减少旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉/ 加上不会影响其他⻋厢每节⻋厢都是独⽴存在的。在链表⾥每节“⻋厢”是什么样的呢3.1.1 结点与顺序表不同的是链表⾥的每节⻋厢都是独⽴申请下来的空间我们称之为“结点/结点”结 点的组成主要有两个部分当前结点要保存的数据和保存下⼀个结点的地址指针变量。图中指针变量plist保存的是第⼀个结点的地址我们称plist此时“指向”第⼀个结点如果我们希望 plist“指向”第⼆个结点时只需要修改plist保存的内容为0x0012FFA0。链表中每个结点都是独⽴申请的即需要插⼊数据时才去申请⼀块结点的空间我们需要通过指针 变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。3.1.2 链表的性质1、链式机构在逻辑上是连续的在物理结构上不⼀定连续 2、结点⼀般是从堆上申请的3、从堆上申请来的空间是按照⼀定策略分配出来的每次申请的空间可能连续可能不连续结合前⾯学到的结构体知识我们可以给出每个结点对应的结构体代码 假设当前保存的结点为整型struct SListNode { int data; //结点数据 struct SListNode* next; //指针变量⽤保存下⼀个结点的地址 };当我们想要保存⼀个整型数据时实际是向操作系统申请了⼀块内存这个内存不仅要保存整型数 据也需要保存下⼀个结点的地址当下⼀个结点为空时保存的地址为空。当我们想要从第⼀个结点⾛到最后⼀个结点时只需要在当前结点拿上下⼀个结点的地址就可以了。3.1.3 链表的打印给定的链表结构中如何实现结点从头到尾的打印思考当我们想保存的数据类型为字符型、浮点型或者其他⾃定义的类型时该如何修改3.2 实现单链表LinkList.h#include stdio.h #include stdlib.h // 定义链表节点结构体 typedef struct MyListNode { int val; struct MyListNode* next; } MyListNode; // 定义链表结构体包含链表长度和虚拟头节点 typedef struct MyLinkedList { int size; MyListNode* dummyHead; } MyLinkedList; // 初始化链表 MyLinkedList* myLinkedListCreate(); // 获取指定下标的值 int myLinkedListGet(MyLinkedList* obj, int index); // 头插法 void myLinkedListAddAtHead(MyLinkedList* obj, int val); // 尾插法 void myLinkedListAddAtTail(MyLinkedList* obj, int val); // 在指定下标插入节点 void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val); // 删除指定下标的节点 void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index); // 打印链表 void myLinkedListPrint(MyLinkedList* obj); // 释放链表 void myLinkedListFree(MyLinkedList* obj);LinkList.c#include LinkList.h // 初始化链表 MyLinkedList* myLinkedListCreate() { MyLinkedList* obj (MyLinkedList*)malloc(sizeof(MyLinkedList)); obj-size 0; obj-dummyHead (MyListNode*)malloc(sizeof(MyListNode)); obj-dummyHead-next NULL; return obj; } // 获取指定下标的值 int myLinkedListGet(MyLinkedList* obj, int index) { if (index 0 || index obj-size) return -1; MyListNode* cur obj-dummyHead-next; for (int i 0; i index; i) { cur cur-next; } return cur-val; } // 头插法 void myLinkedListAddAtHead(MyLinkedList* obj, int val) { MyListNode* newNode (MyListNode*)malloc(sizeof(MyListNode)); newNode-val val; newNode-next obj-dummyHead-next; obj-dummyHead-next newNode; obj-size; } // 尾插法 void myLinkedListAddAtTail(MyLinkedList* obj, int val) { MyListNode* newNode (MyListNode*)malloc(sizeof(MyListNode)); newNode-val val; newNode-next NULL; MyListNode* cur obj-dummyHead; while (cur-next ! NULL) { cur cur-next; } cur-next newNode; obj-size; } // 在指定下标插入节点 void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) { if (index obj-size) return; if (index 0) index 0; MyListNode* newNode (MyListNode*)malloc(sizeof(MyListNode)); newNode-val val; MyListNode* pre obj-dummyHead; for (int i 0; i index; i) { pre pre-next; } newNode-next pre-next; pre-next newNode; obj-size; } // 删除指定下标的节点 void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) { if (index 0 || index obj-size) return; MyListNode* pre obj-dummyHead; for (int i 0; i index; i) { pre pre-next; } MyListNode* temp pre-next; pre-next temp-next; free(temp); obj-size--; } // 打印链表 void myLinkedListPrint(MyLinkedList* obj) { MyListNode* cur obj-dummyHead-next; printf(链表内容); while (cur ! NULL) { printf(%d - , cur-val); cur cur-next; } printf(NULL\n); printf(链表长度%d\n\n, obj-size); } // 释放链表 void myLinkedListFree(MyLinkedList* obj) { MyListNode* cur obj-dummyHead; while (cur ! NULL) { MyListNode* temp cur; cur cur-next; free(temp); } free(obj); }main.c#include LinkList.h int main() { // 创建链表 MyLinkedList* list myLinkedListCreate(); printf( 初始化链表 \n); myLinkedListPrint(list); // 头插法测试 printf( 头插法插入 3, 2, 1 \n); myLinkedListAddAtHead(list, 3); myLinkedListAddAtHead(list, 2); myLinkedListAddAtHead(list, 1); myLinkedListPrint(list); // 尾插法测试 printf( 尾插法插入 4, 5 \n); myLinkedListAddAtTail(list, 4); myLinkedListAddAtTail(list, 5); myLinkedListPrint(list); // 指定位置插入 printf( 下标2处插入 99 \n); myLinkedListAddAtIndex(list, 2, 99); myLinkedListPrint(list); // 获取元素 printf( 获取下标2的值%d \n\n, myLinkedListGet(list, 2)); // 删除元素 printf( 删除下标2的节点 \n); myLinkedListDeleteAtIndex(list, 2); myLinkedListPrint(list); // 释放内存 myLinkedListFree(list); return 0; }运行结果3.3链表的分类链表的结构⾮常多样以下情况组合起来就有8种2x2x2链表结构链表说明虽然有这么多的链表的结构但是我们实际中最常⽤还是两种结构单链表和双向带头循环链表⽆头单向⾮循环链表结构简单⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦结构如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。带头双向循环链表结构最复杂⼀般⽤在单独存储数据。实际中使⽤的链表数据结构都是带头 双向循环链表。另外这个结构虽然结构复杂但是使⽤代码实现以后会发现结构会带来很多优势实 现反⽽简单了后⾯我们代码实现了就知道了。3.4单链表算法题3.4.2设计链表这道题纯基础题来的主要考察基本功。咱们上面的实现单链表的那些接口函数其实就是这道题的答案。因为小编是二刷数据结构了之前没有养成定时总结博客的好习惯。所以现在在恶补博客大家一定要定时总结博客呀。其实我一刷数据结构的时候就卡了好一段时间在链表哈哈哈哈经过几个月的学习现在已经轻车熟路了// 1. 定义链表节点结构体 typedef struct MyListNode { int val; struct MyListNode* next; } MyListNode; // 2. 定义链表本身结构体包含大小和虚拟头节点 typedef struct MyLinkedList{ int size; MyListNode* dummyHead; } MyLinkedList; // 初始化链表 MyLinkedList* myLinkedListCreate() { MyLinkedList* obj (MyLinkedList*)malloc(sizeof(MyLinkedList)); obj-size 0; // 创建虚拟头节点 obj-dummyHead (MyListNode*)malloc(sizeof(MyListNode)); obj-dummyHead-val -1; obj-dummyHead-next NULL; return obj; // 你原本的代码漏了 return } // 获取节点 int myLinkedListGet(MyLinkedList* obj, int index) { // 检查下标是否越界 if (index 0 || index obj-size) { return -1; } // cur 从真正的第一个节点开始 MyListNode* cur obj-dummyHead-next; for (int i 0; i index; i) { cur cur-next; } return cur-val; } // 头插法 void myLinkedListAddAtHead(MyLinkedList* obj, int val) { MyListNode* newNode (MyListNode*)malloc(sizeof(MyListNode)); newNode-val val; newNode-next obj-dummyHead-next; obj-dummyHead-next newNode; obj-size; } // 尾插法 void myLinkedListAddAtTail(MyLinkedList* obj, int val) { MyListNode* cur obj-dummyHead; // 一直往后走直到找到最后一个节点 while (cur-next ! NULL) { cur cur-next; } MyListNode* newNode (MyListNode*)malloc(sizeof(MyListNode)); newNode-val val; newNode-next NULL; cur-next newNode; obj-size; } // 在指定下标插入 void myLinkedListAddAtIndex(MyLinkedList* obj, int index, int val) { if (index obj-size) { return; } if (index 0) { index 0; // 题目说明如果 index 0则在头部插入 } // cur 从虚拟头节点开始走到要插入位置的 前一个节点 MyListNode* cur obj-dummyHead; for (int i 0; i index; i) { cur cur-next; } MyListNode* newNode (MyListNode*)malloc(sizeof(MyListNode)); newNode-val val; newNode-next cur-next; cur-next newNode; obj-size; } // 删除指定下标节点 void myLinkedListDeleteAtIndex(MyLinkedList* obj, int index) { if (index 0 || index obj-size) { return; } // 走到要删除节点的 前一个节点 MyListNode* cur obj-dummyHead; for (int i 0; i index; i) { cur cur-next; } MyListNode* temp cur-next; // temp 就是要删除的节点 cur-next temp-next; free(temp); // 释放内存 obj-size--; } // 释放整个链表 void myLinkedListFree(MyLinkedList* obj) { MyListNode* cur obj-dummyHead; while (cur ! NULL) { MyListNode* temp cur; cur cur-next; free(temp); // 逐个释放节点 } free(obj); // 最后释放链表结构体 }3.4.2移除链表元素移除链表元素/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode dummy {0,head}; //哨兵卫 struct ListNode* cur dummy; while(cur-next){ struct ListNode* nxt cur -next; if(nxt-valval) { cur-next nxt-next; free(nxt); }else{ cur cur-next; } } return dummy.next; }3.4.3反转链表反转链表其实在王道考研数据结构以及课本教材里有讲到关于链表逆序或者称为反转采用头插法可以很容易实现。那么我们采用头插法实现即可代码如下struct ListNode* reverseList(struct ListNode* head) { struct ListNode dummy; dummy.next NULL; struct ListNode* curr head; while(curr) { // 先保存下一个节点 struct ListNode* next curr-next; // 头插curr 插到 dummy 后面 curr-next dummy.next; dummy.next curr; curr next; } return dummy.next; }如果你要问我主播主播你的头插法还是太吃操作了有没有什么更好的方法秒杀这个题。作为一名极客我必须回答有的有的兄弟。对于反转逆置链表我们有三种方法除了上面的头插我们还有迭代递归。其实简单讲就是利用几个指针断开旧链生成新链。最终返回目标链表迭代法struct ListNode* reverseList(struct ListNode* head) { struct ListNode* prev NULL; struct ListNode* curr head; while (curr) { struct ListNode* next curr-next; curr-next prev; prev curr; curr next; } return prev; }递归法递归走到链表最后一个节点新头回溯时让后一个节点指向自己自身指向 NULL。struct ListNode* reverseList(struct ListNode* head) { // 递归终止空节点 / 只剩一个节点直接返回 if(head NULL || head-next NULL) { return head; } // 递归拿到反转后的新头原最后一个节点 struct ListNode* newHead reverseList(head-next); // 反转指向后一个节点指向当前节点 head-next-next head; // 当前节点断开原指向防止环 head-next NULL; // 始终返回新头 return newHead; }走一遍 [1,2,3] 逻辑reverse (1) → 调用 reverse (2) → 调用 reverse (3)reverse (3)3-nextNULL返回 newHead3回到 reverse (2)2-next-next 2 → 3→22-nextNULL返回 newHead3回到 reverse (1)1-next-next 1 →2→11-nextNULL返回 newHead3你要问我这道题还有没有别的方法我其实还有一些暴力方法比如利用栈的后进先出特性可以很好的暴力解决这个问题但考虑到目前我还没更新到栈可能有某些小伙伴看不懂等我后面更新到栈的时候我再讲一下用栈的思想解决这个题。3.4.4 链表的中间结点876. 链表的中间结点 - 力扣LeetCode这是一道经典的链表问题为什么经典呢可能有些小伙伴会疑惑我该怎么利用链表的特性寻找中间节点呢或许我们可以尝试暴力遍历统计总共有多少个节点记作sum然后根据sum进行遍历求解中间节点。非常好你已经具有暴力思维再也不是那个一看见算法题就放弃的娃娃了。其实这段话是对过去的我说的哈哈哈哈哈/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* middleNode(struct ListNode* head) { int n0; struct ListNode* cur head; while(cur!NULL){ n; curcur-next; } int k0; curhead; while(kn/2){ k; curcur-next; } return cur; }但是有一句很有意思的话五十步笑一百步。我们可以利用快慢双指针一个快fast指针一个慢slow指针。让fast每一次走2步slow每一次走1步当fast走到链表末尾时或者快到末尾时这个时候因为fast-next-next null我们不准fast继续往下走了slow所在位置就是中间节点。代码如下class Solution { public: ListNode* middleNode(ListNode* head) { ListNode* slow head; ListNode* fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } return slow; } };后续有关链表的做题思路解题技巧以及项目里的具体应用我会逐一更新在这个账号敬请期待欢迎一同学习与交流