无锡网站建设专注千客云网络,怎么看网站是谁家做的,外贸业务员面试常见问题,网站极速备案写在前面
本篇笔记记录线性表——链表的主要形式#xff0c;虽然链表有8种形式#xff0c;但是只要精通笔记中编写的两种#xff0c;即可触类旁通。 文章目录 写在前面一、链表的概念及结构二、链表的分类三、无头单向非循环链表3.1、链表的实现3.1.1、链表的结构体定义3.1…写在前面
本篇笔记记录线性表——链表的主要形式虽然链表有8种形式但是只要精通笔记中编写的两种即可触类旁通。 文章目录 写在前面一、链表的概念及结构二、链表的分类三、无头单向非循环链表3.1、链表的实现3.1.1、链表的结构体定义3.1.2、动态申请一个节点3.1.3、单链表打印3.1.4、单链表尾插3.1.5、单链表的头插3.1.6、单链表的尾删3.1.7、单链表头删3.1.8、单链表查找3.1.9、单链表在pos位置之后插入x3.1.10、单链表删除pos位置之后的值3.1.11、链表的销毁3.1.12、单链表在pos的前面插入3.1.13、删除pos位置 3.2、OJ练习3.2.1、反转链表3.2.2、相交链表3.2.3、 环形链表 II3.2.4、随机链表的复制 四、带头双向循环链表4.1、带头双向循环链表的实现4.1.1、链表的结构体定义4.1.2、创建返回链表的头结点.4.1.3、双向链表销毁4.1.4、双向链表打印4.1.5、 双向链表尾插4.1.6、双向链表尾删4.1.7、双向链表头插4.1.8、双向链表头删4.1.9、双向链表查找4.1.10、双向链表在pos的前面进行插入4.1.11、双向链表删除pos位置的节点 4.2、优化带头双向循环链表的实现4.2.1、优化后的双向链表尾插4.2.2、优化后的双向链表尾删4.2.3、优化后的双向链表头插4.2.4、优化后的双向链表头删 5.顺序表和链表的区别 一、链表的概念及结构 概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 逻辑结构是程序猿们为了更直观的理解而画出来的结构。在真实的内存存储中并无这样。
二、链表的分类 实际中链表的结构非常多样以下情况组合起来就有8种链表结构 一、单向或者双向 二、带头或者不带头有无哨兵位 三、循环或者非循环 在上面介绍的三大类中相互结合可以得到 23 种结合方式。
虽然有这么多的链表的结构但是我们实际中最常用还是两种结构
无头单向非循环链表带头双向循环链表(在掌握后可以20分钟内手撕出来) 三、无头单向非循环链表 结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。又因为无法通过当前节点找到前节点的地址所以这种结构在笔试面试考试中出现很多。只要是考察单链表的就是考察这个。如下图 3.1、链表的实现
链表的实现链表的命名规则借鉴c中的stl库
3.1.1、链表的结构体定义
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;typedef int SLTDateType;把链表结构的类型重命名为SLTDateType。若将来如果要改变链表内容的结构类型就可以极为方便的改变。在结构体中定义了链表的存储的内容与存储下个节点的指针。为了更方便使用链表结构体把链表结构体重命名为SListNode。
3.1.2、动态申请一个节点
SListNode* BuySListNode(SLTDateType x) {SListNode* ma (SListNode*)malloc(sizeof(SListNode));if (ma NULL) {perror(malloc in BuySListNode::);}ma-data x;ma-next NULL;return ma;
}因为我们要实现的是无头单向非循环链表所以只有插入一个节点时候才会申请一个节点所以我们就需要设置一个形参用来接收插入的内容。在申请一个节点时我们不知道该节点需要存放在哪个位置为了避免野指针所以我们统一把next设为NULL在调用BuySListNode之后程序猿根据自己的需求来调整next指针。
3.1.3、单链表打印
void SListPrint(SListNode* plist) {printf(内容为:);SListNode* p1 plist;while (p1) {printf(%d , p1-data);p1 p1-next;}printf(\n);
}我们只需要循环遍历链表把链表的值打印出来即可。循环条件设置为指针当指针为NULL时证明链表已经结束并且循环条件为NULL时判定为假为假结束循环。
3.1.4、单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x) {SListNode* capacity BuySListNode(x);SListNode* ptr1 *pplist;if (*pplist NULL) {*pplist capacity;}else {while (ptr1-next ! NULL) {ptr1 ptr1-next;}ptr1-next capacity;}
}需要使用二级指针来接收链表的地址因为只有二级指针才可以访问到链表的指针。只有链表的指针才可以依此访问链表的内容。如下图 把需要插入的x值传递给BuySListNode函数开辟一个节点。 在尾插之前我们需要判断*pplist是否为NULL如为NULL说明链表里面目前没有一个节点那就需要把*pplist赋值为头的节点 判断了*pplist不为NULL则循环查找找到ptr1-next值为NULL即找到链表最后一个节点。 在找到链表最后一个节点后把新开辟的节点的地址赋值给该节点的next值即完成了链接。
3.1.5、单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x) {assert(pplist);SListNode* capacity BuySListNode(x);if (pplist NULL) {*pplist capacity;}else {capacity-next (*pplist);*pplist capacity;}
}把需要插入的x值传递给BuySListNode函数开辟一个节点。在头插之前我们需要判断*pplist是否为NULL如为NULL说明链表里面目前没有一个节点那就需要把*pplist赋值为头的节点判断了*pplist不为NULL则把新开辟的节点的next值存放*pplist然后再把*pplist指向新开辟的节点这样就完成头插了。
3.1.6、单链表的尾删
void SListPopBack(SListNode** pplist) {assert(*pplist);int i 0;SListNode* prev *pplist;SListNode* ptr1 *pplist;if (ptr1-next NULL) {free(ptr1);*pplist NULL;return;}while(ptr1-next){prev ptr1;ptr1 ptr1-next;}prev-next NULL;free(ptr1);
}先用断言assert判断链表是否是NULL如果为空就报错。(你空的你还删什么)因为单链表无法在当前节点找到上一个节点的位置所以需要两个指针一个记录当前节点(ptr1)一个记录上一个节点(prev)在删除节点前我们需要判断一下当前链表是否只剩下一个节点如果只剩下一个节点就直接free掉把*pplist赋值为空即可。如果链表还剩下不止一个节点时我们就循环找到尾部通过prev ptr1;与ptr1 ptr1-next;的搭配可以把prev永远设为ptr1的上一个节点把prev的next赋值为空之后free掉尾节点完成尾删。prev ptr1;与ptr1 ptr1-next;的搭配在第一次进入循环语句是ptr1与prev是同一指向链表的头节点的之后ptr1再指向下一个节点这样就把ptr1变为了next节点到最后ptr1-next为空时不再进入循环那此时ptr1就指向尾节点prev还是指向ptr1的上一个节点。
3.1.7、单链表头删
void SListPopFront(SListNode** pplist) {assert(*pplist); SListNode* Next (*pplist)-next;free(*pplist);*pplist Next;
}先用断言assert判断链表是否是NULL如果为空就报错。(你空的你还删什么)创建一个Next指针指向当前节点的next节点之后直接free掉*pplist就可以完成头节点的删除了但是别忘记把Next赋值给*pplist指针完成链表头节点的重定位。在上述头删代码中 如果只有一个节点的情况也是可以正常运行的因为只有一个节点时头节点的next值是NULL在free掉头节点后把Next赋值给*pplist指针也是把*pplist定为了NULL。
3.1.8、单链表查找
SListNode* SListFind(SListNode* plist,const SLTDateType x) {assert(plist);while (plist) {if (plist-data ! x) {plist plist-next;}else {return plist;}}return NULL;
}先用断言assert判断链表是否是NULL如果为空就报错。(你空的你还找什么)循环遍历即可。
3.1.9、单链表在pos位置之后插入x 如果在pos位置之前插入要脑筋急转弯一下(我们后面实现在位置之前插入) void SListInsertAfter(SListNode* pos, SLTDateType x) {assert(pos);SListNode* p1 pos;SListNode* capacity BuySListNode(x);capacity-next p1-next;p1-next capacity;
}先用断言assert判断链表是否是NULL如果为空就报错。(你空的哪有什么pos位置)把需要插入的x值传递给BuySListNode函数开辟一个节点。把当前节点的next值赋值给新开辟的节点的next。这样不会丢失pos之后的链表如下图。把capacity的next成功链接到pos节点后的链表后我们再把pos节点的next值指向capacity。这样就完成在pos位置之后插入x如下图。
3.1.10、单链表删除pos位置之后的值 如果删除pos位置节点需要脑筋急转弯一下(我们后面实现删除pos位置节点) void SListEraseAfter(SListNode* pos) {assert(pos pos-next);SListNode* Next pos-next;pos-next Next-next;free(Next);
}先用断言assert判断链表头节点与头节点的下一个节点是否是NULL如果为空就报错。(你都没有两个节点哪有什么pos之后位置)定义一个值记录pos的下一个节点把pos节点的next值存放Next-next值后就链接上了头节点的下一个节点的之后的链表(如下图)。在连接成功后我们就直接free掉Next即可完成删除pos位置之后的值。
3.1.11、链表的销毁 链表的销毁非常简单遍历free即可。 void SLTDestroy(SListNode** pphead) {SListNode* p1 (*pphead)-next;while (*pphead) {free(*pphead);*pphead p1;if (*pphead ! NULL) {p1 (*pphead)-next;}}
}注意的是需提前记录要释放的节点的下一个节点。
3.1.12、单链表在pos的前面插入
void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x) {assert(*pphead);SListNode* prev *pphead;while (prev-next ! pos) {prev prev-next;}SListNode* p1 BuySListNode(x);p1-next prev-next;prev-next p1;
}在经历了完成链表的实现后我们再看上述代码就轻松多了。只要把prev节点控制在pos节点前一个节点我们就使用和尾插相同的逻辑就可以实现pos的前面插入
3.1.13、删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos) {assert(*pphead);SListNode* prev *pphead;while(prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);
}在经历了完成链表的实现后我们再看上述代码就轻松多了。只要把prev节点控制在pos节点前一个节点再使用和尾删相同的逻辑就可以实现删除pos位置
3.2、OJ练习 为了更好的理解单链表我们尝试几道OJ题。 3.2.1、反转链表 反转链表的连接(点我跳转) 给你单链表的头节点 head 请你反转链表并返回反转后的链表。
示例 1 输入head [1,2,3,4,5] 输出[5,4,3,2,1] 示例代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {}解析
方法一
head指针肯定是指向链表头节点的题目要求我们反转链表我们可以新建一个空链表然后使用头插即可完成该题。但是很有局限性这个方法的时间复杂度和空间复杂度都是O(n)
方法二(推荐)
我们定义三个指针分别记录原链表中的当前节点、prev节点与Next节点之后我们反转当前节点、prev节点指针的指向这样就完成了链表的反转反转后我们还保留了原链表中Next节点在Next节点之后的链表是未进行反转的我们利用保留的Next节点重新分配当前节点、prev节点与Next节点循环操作即可把链表实现时间复杂度O(n)和空间复杂度O(1)的反转链表
struct ListNode* reverseList(struct ListNode* head) {// 初始化新链表头newHead指针1ptr1指向原链表的头部Next用于保存下一个节点struct ListNode *newHead NULL, *ptr1 head, *Next NULL;// 遍历原链表逐个反转节点的指向while (ptr1) {Next ptr1-next; // 暂存当前节点的下一个节点避免丢失ptr1-next newHead; // 将当前节点的next指向newHead反转指针newHead ptr1; // 更新newHead指向当前节点原链表中的节点变成了新链表的节点ptr1 Next; // 移动ptr1指针指向原链表的下一个节点}// 返回新的链表头即原链表的尾部return newHead;
}在上面代码中prev被newHead所替代ptr1代表的是当前的节点 head不为空的情况在第一次进入循环时我们先让Next节点记录原链表。确保反转后还可以正常进行。如下图 我们把第一个节点的next指向newHead此时newHead为空如下图这样就成功反转头节点的指向。 接下来把newHead指向ptr1保证ptr1回到原链表后在初始链表中newHead还是ptr1的上一个节点完成利用保留的Next节点重新分配ptr1节点(如下图)就把当前节点ptr1成返回到未反转指针的链表中。 判断ptr1是否为NULL即可判断未反转的链表是否结束 循环操作当然一上来肯定是先让Next节点记录原链表。确保反转后还可以正常进行。把当前节点ptr1的next指向newHead此时newHead为初始链表时ptr1的上一个节点如下图这样就成功反转头节点的指向。 接下来把newHead指向ptr1保证ptr1回到原链表后在初始链表中newHead还是ptr1的上一个节点完成利用保留的Next节点重新分配ptr1节点(如下图)就把当前节点ptr1成返回到未反转指针的链表中。 如此循环直到ptr1为NULL时结束反转此时我们就得到了反转后链表的头节点newHead(如下图)。 head为空的情况)在head为空是ptr1节点也为NULL不会进入循环我们在赋初值时就把newHead赋值为NULL此时我们直接返回newHead也是正确。 3.2.2、相交链表 反转链表的连接(点我跳转) 给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。
图示两个链表在节点 c1 开始相交 题目数据 保证 整个链式结构中不存在环。 示例 1
注意函数返回结果后链表必须 保持其原始结构 。 输入intersectVal 8, listA [4,1,8,4,5], listB [5,6,1,8,4,5], skipA 2, skipB 3 输出Intersected at ‘8’ 示例代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {}解析
在题目图示中可以看到图示代码中有三组链表其中链表a与b相交点是链表c。但是正常遍历比较判断是无法判断出相交点因为a与b链表的长度不一。
解题方法
先求出两个数组的长度。之后求出长度差。把长度长的链表先运行长度差个节点。之后一起运行。确保两个链表从剩余长度相同的地方开始比较。在同时运行过程中我们每次都判断节点的地址是否相同若相同时说明该节点相交。如果遍历完成仍没有找到交点则返回NULL说明两个链表没有交点。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {// 如果其中一个链表为空返回NULL没有交点if (headA NULL || headB NULL) {return NULL;}// 定义计数器i和j分别用于记录链表A和链表B的长度int i 0, j 0;// 创建两个指针分别指向链表A和链表B的头节点struct ListNode *newa headA, *newb headB;// 计算链表A的长度while (newa) {i; // 计数器i加1newa newa-next; // 移动指针到下一个节点}// 计算链表B的长度while (newb) {j; // 计数器j加1newb newb-next; // 移动指针到下一个节点}// 创建两个指针分别指向链表A和链表B的头节点struct ListNode *pa headA, *pb headB;// 如果链表A比链表B长先移动链表A的指针使两个链表剩余部分长度相等if (i j) {int num i - j; // 计算链表A比链表B长的差距while (num) { // 移动链表A的指针直到两个链表剩余部分长度相同pa pa-next;num num - 1; // 差距减少1}}// 如果链表B比链表A长先移动链表B的指针使两个链表剩余部分长度相等else if (j i) {int num j - i; // 计算链表B比链表A长的差距while (num) { // 移动链表B的指针直到两个链表剩余部分长度相同pb pb-next;num num - 1; // 差距减少1}}// 现在链表A和链表B的剩余部分长度相同从头开始比较while (pa ! NULL) {if (pa pb) { // 如果两个指针指向同一个节点说明找到了交点return pa; // 返回交点节点} else { // 如果没有找到交点继续向后移动pa pa-next;pb pb-next;}}// 如果遍历到末尾没有找到交点返回NULLreturn NULL;
} 3.2.3、 环形链表 II 反转链表的连接(点我跳转) 给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1 输入head [3,2,0,-4], pos 1 输出返回索引为 1 的链表节点 解释链表中有一个环其尾部连接到第二个节点。 解析
此题主要考察的是在环中怎么找到环的起始点。简化上图我们在新画的图中寻找规律(如下图)首先我们需要先使用快慢指针来判断这是否是一个有环的链表(快慢指针中快指针为fast、慢指针为slow**。slow指针每次移动一步fast指针每次移动两步。)如果是有环链表快慢指针在环中一定会相交(如下图) **我们现在设 不是环的链表的长度为:L、环的周长为:C、入环点交点到快门指针交点长度为N(如图)根据上图中的标记我们列出快指针和慢指针在相遇时的方程(在相遇前我们不知道快指针在环内转了多少圈设转了X圈)fast LX*C Nslow L N根据快门指针的特性快指针是慢指针的二倍)我们可以得到如下公式fast 2*slow。即 LX*C N 2 * ( L N)。我们逐步化简公式(如下图)因为我们要求入环点观看图一(鼠标移动到图片有提示) 可以看到入环点是不是环的链表的长度L即在L处相交就是入环点 。据上图公式为了求出长度L只有在相交点处开始运行才比能在入环点处多走N步多走N步后才能抵消-N带来的影响那此时我们上图的公式就变为了LX*C。又因为N是入环点到快慢指针的相交点的距离说明找入环点指针的起始点必须在快慢指针的相交点才能求出入环点。此时我们只需要定义一个指针在链表开头开始逐步往后运行定义一个指针在快慢指针的相交点处开始逐步运行两个指针相交的时刻即为链表的入环点。
解题方法
先求出找到快门指针的交点。之后分别定义两个指针一个在链表开头开始逐步往后运行一个指针在快慢指针的相交点处开始逐步运行。
struct ListNode* detectCycle(struct ListNode* head) {// 如果链表为空或只有一个节点即没有环直接返回NULLif (head NULL || head-next NULL) {return NULL;}// 定义快慢指针和辅助指针struct ListNode *slow, *fast, *ptr;// 初始化慢指针和快指针都指向链表头slow head;fast head;// 使用快慢指针检测环while (fast) {slow slow-next; // 慢指针每次走一步ptr fast-next; // 临时保存快指针的下一个节点if (ptr NULL) { // 如果快指针走到末尾则没有环返回NULLreturn NULL;}fast ptr-next; // 快指针每次走两步// 如果快慢指针相遇说明链表有环if (slow fast) {// 如果有环从链表头开始与慢指针一起移动找到环的入口节点struct ListNode* intersect head;while (intersect ! slow) { // 当相遇时intersect节点就是环的入口节点intersect intersect-next;slow slow-next;}return intersect; // 返回环的入口节点}}// 如果没有环返回NULLreturn NULL;
}因为slow指针就是在链表相交点并且是逐步运行的所以我们可以使用slow指针充当在快慢指针的相交点处开始逐步运行的指针。 3.2.4、随机链表的复制 反转链表的连接(点我跳转) 给你一个长度为 n的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如如果原链表中有 X 和 Y 两个节点其中 X.random -- Y 。那么在复制链表中对应的两个节点 x 和 y 同样有 x.random -- y 。
返回复制链表的头节点。
示例 1 输入head [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出[[7,null],[13,0],[11,4],[10,2],[1,0]] 示例代码
/*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {}解析
在数据结构中没有说绝对使用某一种算法或链表适当时候可以灵活应用本题创建一个哨兵节点会省事很多。
方法一(不推荐)
首先创建一个链表用来记录原链表的val值和next值。之后再返回原链表的头节点head通过原链表原有的random指向确认每一个节点的random指针指向哪个节点后保留该节点到指向节点的距离镜像对比来找出深拷贝链表中random指针指向的节点。但是很有局限性这个方法的时间复杂度是O(n) 但是 空间复杂度是O(n2)。
代码实现
struct Node* getTail(){struct Node* newt (struct Node*)malloc(sizeof(struct Node));if(newt NULL){perror(malloc in getTail::);}return newt;
}struct Node* copyRandomList(struct Node* head) {int num 0;struct Node* ptr1 head;struct Node* newhead getTail();//创建哨兵 struct Node* nh1 newhead;if (head NULL) {return NULL;}while (ptr1) {//计算原链表有多少个节点num;ptr1 ptr1-next;}int numsz num;//保存原链表的长度ptr1 head;while (numsz--) {//完成新链表的创建与val的赋值struct Node* ptr2 getTail();ptr2-val ptr1-val;nh1-next ptr2; //新链表相连nh1 nh1-next;ptr1 ptr1-next;}nh1-next NULL;numsz num;ptr1 head;//把ptr1重新指向头节点struct Node* pnh1 newhead-next;//创建一个指针指向新链表的哨兵位的下一位struct Node* ptr2 newhead-next;//改变pandom的指针定位while (numsz--) {//完成random的赋值pnh1 newhead;//每完成一个就回到哨兵节点if (ptr1-random NULL) {ptr2-random NULL;}else {//struct Node* p ptr1-random;//记录原指针的randomstruct Node* p2 head;//使用p2来找到ptr1的randomint i 1;//记录random是在第几个while (p2 ! ptr1-random) {p2 p2-next;i;}while (i--) {pnh1 pnh1-next;//运行到对应的random}ptr2-random pnh1;}ptr1 ptr1-next;ptr2 ptr2-next;}ptr2 newhead-next;free(newhead);newhead ptr2;return newhead;
}方法二(推荐)
在每个需要深拷贝的节点后我们使用尾插的方式插入一个节点到原数组中尾插后的节点保存上一个节点的所有值。在成功尾插后我们进行random的赋值因为我们深拷贝的节点是尾插的所以所有的random节点的Next节点都是深拷贝所对应的random节点。在循环赋值完所有深拷贝节点的random指针后我们再回复链表使得链表与原链表一样。这样我们程序的时间复杂度是和空间复杂度都是O(n)了。
代码实现
//动态分配一个新节点并返回
struct Node* getTail(){struct Node* newt (struct Node*)malloc(sizeof(struct Node)); // 分配内存if(newt NULL){ // 如果内存分配失败打印错误信息perror(malloc in getTail::);}return newt; // 返回新分配的节点
}struct Node* copyRandomList(struct Node* head) {struct Node* ptr1 head;// 第一阶段创建新节点并插入到原链表的每个节点后面while(ptr1) { struct Node* newnode getTail(); // 获取一个新节点newnode-next ptr1-next; // 新节点的next指向原节点的nextptr1-next newnode; // 将新节点插入到原节点之后newnode-val ptr1-val; // 将原节点的值赋给新节点ptr1 newnode-next; // 将ptr1指向原链表中的下一个节点}ptr1 head; // 将ptr1重新定位到链表的头部// 第二阶段复制random指针while(ptr1) {struct Node* Next ptr1-next; // 记录深拷贝的节点if(ptr1-random NULL) {Next-random NULL; // 如果原节点的random为空复制到NULL} else {Next-random ptr1-random-next; // 将原节点的random指向的节点的下一个节点赋值给新节点的random}ptr1 Next-next; // 将ptr1指向原链表中的下一个节点}struct Node* newHead NULL, *ptr2 NULL;ptr1 head; // 将ptr1重新定位到链表的头部// 第三阶段拆分新链表和恢复原链表while(ptr1) {if(newHead NULL) {newHead ptr1-next; // 新链表的头是原链表的第一个新节点ptr2 newHead; // 设置ptr2为新链表的尾部} else {ptr2-next ptr1-next; // 将新链表的尾部指向当前新节点ptr2 ptr2-next; // 更新ptr2为新链表的尾部}ptr1-next ptr2-next; // 恢复原链表跳过新节点ptr1 ptr1-next; // 将ptr1指向原链表的下一个节点}return newHead; // 返回深拷贝后的新链表头
} 第一阶段创建新节点插入到原链表的每个节点后面并拷贝val值。如下图循环操作把每个深拷贝节点都插入到原链表的每个节点后面如下图 在第一阶段完成后得到的好处是在每个深拷贝的节点都是原链表节点的next节点这样做可以得到原链表指的random节点对应的深拷贝节点位置就是random-next这样就不需要方法一中的第二层循环去查找每个random的深拷贝节点实现时间复杂度为O(N)。 进入第二阶段复制random指针。通过原链表找到对应的random指针。如下图在找到原链表ptr1指针的random节点后先判断ptr1-random节点是否为空如果位空就直接把深拷贝节点ptr1-next的random赋值为NULL。 在原链表当前节点完成深拷贝节点random赋值后我们需要进入下一个原链表的节点因为每个原链表节点后面都有一个深拷贝链表并且每个深拷贝节点的next值都是原链表节点的next值所以ptr1指针每次向后运行都是ptr1 Next-next;在进行循环的第一个指令就把struct Node* Next ptr1-next; 进入下一个原链表的节点后还是先判断ptr1-random节点是否为空如果不为空我们原链表的next节点对应的就是深拷贝的节点赋值给深拷贝的random节点。即Next-random ptr1-random-next;如下图如此循环即可把所有深拷贝节点的random赋值完成。 之后我们进入 第三阶段拆分新链表和恢复原链表。我们只需要定义一个深拷贝链表的头节点newHead和用来动态指向深拷贝节点的指针ptr2之后再依此断开即可。 若newHead为NULL如下图将ptr1指向原链表的下一个节点如下图 之后newHead不为NULL此时就需要ptr2的next指向ptr1节点的深拷贝节点即ptr2-next ptr1-next;如下图之后再移动ptr2指向深拷贝链表的最后一个节点。ptr2 ptr2-next;如下图 之后循环即可完成所以的操作。如下图 四、带头双向循环链表 结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了。 在数据结构中没有说绝对使用某一种算法或链表适当时候可以灵活应用在双向循环链表创建一个哨兵节点会省事很多。 在带头双向循环链表中我们判断链表位空的条件就是head head-next因为自己连接自己时只剩下哨兵节点。如下图
4.1、带头双向循环链表的实现 其中与单链表相同的部分就不再对代码进行解析 4.1.1、链表的结构体定义
typedef int LTDataType;
typedef struct ListNode
{LTDataType _data;struct ListNode* _next;struct ListNode* _prev;
}ListNode;4.1.2、创建返回链表的头结点.
ListNode* ListCreate() {ListNode* p1 (ListNode*)malloc(sizeof(ListNode));if (p1 NULL) {perror(malloc in ListCreate::);}p1-_data 0;p1-_next p1;p1-_prev p1;return p1;
}4.1.3、双向链表销毁
void ListDestory(ListNode* pHead) {assert(pHead);ListNode* next pHead-_next;while (next ! pHead) {pHead-_prev next-_prev;next-_prev-_next pHead;free(next);next pHead-_prev;}
}在带头双向循环链表中我们判断链表位空的条件就是next ! pHead因为自己连接自己时只剩下哨兵节点。在每次销毁节点前都需要把前一个节点的next值保存被销毁节点的next值如下图。在记录完成后我们也要把d3节点的prev节点连接上d1节点只有这两步骤完成了才可以确保链表的连续性如下图。在正确连接后我们就可以安心free了如此循环直到只剩下哨兵位则说明链表的节点已经被销毁。
4.1.4、双向链表打印
void ListPrint(ListNode* pHead) {assert(pHead);ListNode* next pHead-_next;while (next ! pHead) {printf(%d , next-_data);next next-_next;}printf(\n);
}4.1.5、 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x) {assert(pHead); // 确保pHead指针不为空// 创建一个新的节点ListNode* p1 ListCreate();p1-_data x; // 设置新节点的数据字段为x// 将新节点插入到双向链表的尾部p1-_prev pHead-_prev; // 新节点的前驱是原链表尾节点p1-_next pHead; // 新节点的后继是头节点pHeadpHead-_prev-_next p1; // 原尾节点的next指向新节点pHead-_prev p1; // pHead的前驱指向新节点
}
与单链表插入并无两样只是增加了prev指针必须确保链表的连续。
4.1.6、双向链表尾删
void ListPopBack(ListNode* pHead) {assert(pHead);ListNode* tail pHead-_prev;if (tail ! pHead) {pHead-_prev tail-_prev;tail-_prev-_next pHead;free(tail);}
}与双向链表销毁逻辑如出一辙。
4.1.7、双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x) {assert(pHead);ListNode* p1 ListCreate();p1-_data x;p1-_next pHead-_next;pHead-_next-_prev p1;pHead-_next p1;p1-_prev pHead;}与尾插入逻辑一样
4.1.8、双向链表头删
void ListPopFront(ListNode* pHead) {assert(pHead);ListNode* next pHead-_next;if (next ! pHead) {next-_next-_prev pHead;pHead-_next next-_next;free(next);}}与尾删逻辑一样
4.1.9、双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x) {assert(pHead);ListNode* next pHead-_next;while (next ! pHead) {if (next-_data x) {return next;}next next-_next;}return NULL;
}4.1.10、双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x) {ListNode* p1 ListCreate();p1-_data x;pos-_prev-_next p1;p1-_next pos;p1-_prev pos-_prev;pos-_prev p1;
}与尾插入逻辑一样
4.1.11、双向链表删除pos位置的节点
void ListErase(ListNode* pos) {assert(pos);if (pos-_prev pos) {return;}pos-_prev-_next pos-_next;pos-_next-_prev pos-_prev;free(pos);
}与尾删逻辑一样
4.2、优化带头双向循环链表的实现 在上面实现的过程中我们可以发现插入和删除的逻辑时一样的只是位置有些许差异。代码非常耦合这时候我们只需要实现双向链表在pos的前面进行插入和双向链表删除pos位置的节点其他的插入删除代码只需要调用即可。完成所有的插入与删除。 4.2.1、优化后的双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x) {assert(pHead);ListInsert(pHead, x);
}根据带头双向循环链表的特性哨兵节点的prev就是链表的尾节点所以我们把头节点传入函数ListInsert()在pos的前面进行插入函数即可完成尾插。
4.2.2、优化后的双向链表尾删
void ListPopBack(ListNode* pHead) {assert(pHead);ListErase(pHead-_prev);
}根据带头双向循环链表的特性哨兵节点的prev就是链表的尾节点所以我们把头节点的prev传入函数ListErase()删除pos位置的节点即可完成尾删。
4.2.3、优化后的双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x) {assert(pHead);ListInsert(pHead-_next, x);
}因为有哨兵位所以把头节点的next传到ListInsert()函数即可完成头插。
4.2.4、优化后的双向链表头删
void ListPopFront(ListNode* pHead) {assert(pHead);ListErase(pHead-_next);
}因为有哨兵位所以把头节点的next传到ListErase()函数即可完成头删。
这样的话我们只要实现带头双向循环链表的ListErase()和ListInsert()函数就可以完成6个函数对比起其他链表的实现效率高了不止一点半星。
5.顺序表和链表的区别
不同点顺序表链表存储空间上物理上一定连续逻辑上连续但物理上不一定连续随机访问支持O(1)不支持: O(N)任意位置插入或者删除元素可能需要搬移元素效率低O(N)只需修改指针指向插入动态顺序表空间不够时需要扩容没有容量的概念应用场景元素高效存储频繁访问任意位置插入和删除频繁缓存利用率高低
注意缓存利用率参考存储体系结构 以及 局部原理性。
链表和顺序表中不存在谁替代谁只有双剑合璧才能破敌万千。 以上就是本章所有内容。若有勘误请私信不才。万分感激 如果对大家有帮助的话就请多多为我点赞收藏吧~~~
ps:表情包来自网络侵删
