【数据结构】线性表——链表

写在前面

本篇笔记记录线性表——链表的主要形式，虽然链表有8种形式，但是只要精通笔记中编写的两种，即可触类旁通。

---

---

一、链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

逻辑结构是程序猿们为了更直观的理解而画出来的结构。在真实的内存存储中并无这样。

二、链表的分类

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

一、单向或者双向

二、带头或者不带头（有无哨兵位）

三、循环或者非循环

在上面介绍的三大类中，相互结合可以得到 2³ 种结合方式。

虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

• 无头单向非循环链表
• 带头双向循环链表(在掌握后，可以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)

方法二：(推荐)

1. 我们定义三个指针，分别记录原链表中的当前节点、prev节点与Next节点，之后我们反转当前节点、prev节点指针的指向，这样就完成了链表的反转，反转后我们还保留了原链表中Next节点，在Next节点之后的链表是未进行反转的
2. 我们利用保留的Next节点，重新分配当前节点、prev节点与Next节点，循环操作，即可把链表实现时间复杂度O(n)和空间复杂度O(1)的反转链表

struct ListNode* reverseList(struct ListNode* head) {// 初始化新链表头（newHead），指针1（ptr1）指向原链表的头部，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链表的长度不一。

解题方法：

1. 先求出两个数组的长度。
2. 之后求出长度差。
3. 把长度长的链表先运行长度差个节点。之后一起运行。确保两个链表从剩余长度相同的地方开始比较。
4. 在同时运行过程中，我们每次都判断节点的地址是否相同，若相同时，说明该节点相交。
5. 如果遍历完成仍没有找到交点，则返回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 = L+X*C+ N；slow = L + N
• 根据快门指针的特性（快指针是慢指针的二倍)，我们可以得到如下公式：fast =2*slow。即： L+X*C+ N = 2 * ( L + N)。
• 我们逐步化简公式：(如下图)
• 因为我们要求入环点：观看图一(鼠标移动到图片有提示) 可以看到入环点是不是环的链表的长度L，即在L处相交就是入环点 。
• 据上图公式，为了求出长度L，只有在相交点处开始运行才比能在入环点处多走N步，多走N步后才能抵消-N带来的影响，那此时，我们上图的公式就变为了：L=X*C。又因为N是入环点到快慢指针的相交点的距离，说明找入环点指针的起始点必须在快慢指针的相交点才能求出入环点。
• 此时我们只需要定义一个指针在链表开头开始逐步往后运行，定义一个指针在快慢指针的相交点处开始逐步运行，两个指针相交的时刻即为链表的入环点。

解题方法：

1. 先求出找到快门指针的交点。
2. 之后分别定义两个指针，一个在链表开头开始逐步往后运行，一个指针在快慢指针的相交点处开始逐步运行。

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(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) {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;  // 新节点的后继是头节点（pHead）pHead->_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:表情包来自网络，侵删🌹