数据结构：双向链表（2）

ListNode* LTFind(ListNode* h, type x) { if (LTEmpty(h)) { return NULL; } ListNode* p = h->next; while (p != h) { if (p->data == x) { return p; } p = p->next; } return NULL; }

细讲：

通过遍历来实现，如果在遍历过程中找到了我们需要查找的数据就返回当前位置的节点，没有就返回空。

2.双向链表在指定位置插入

双向链表在指定位置插入分为双向链表在指定位置之前插入与双向链表在指定位置之后插入：

双向链表在指定位置之后插入

函数形式：

void LTInsert(ListNode* pos, type x)

实现：

void LTInsert(ListNode* pos, type x) { assert(pos); ListNode* p = pos->next; ListNode* newnode = LTcreat(x); pos->next = newnode; newnode->prev = pos; newnode->next = p; p->prev = newnode; }

细讲：该函数用于在双向链表的 指定节点 pos 之后插入新节点，核心逻辑是通过调整指针关系实现无缝插入。

1.参数与前置检查作用：pos 是插入位置的基准节点（新节点将插入其后），x 是新节点的数据。风险控制：assert(pos) 防止用户传入 nullptr 导致后续操作崩溃。

2. 保存后继节点必要性：插入新节点后，pos 的 next 指针会指向新节点，若不提前保存原后继 pos->next，将导致原链表后半部分丢失。

核心：调整指针关系（4步插入法）

在指定位置之后的插入操作其实也没有很难，还是先断言，后续就是先申请一个新节点，跟头插尾插相似的方式。

双向链表在指定位置之前插入

函数形式：

void LTInsertfront(ListNode* pos, type x);

实现：

void LTInsertfront(ListNode* h, ListNode* pos, type x) { if (LTEmpty(h)) { return ; } ListNode* p = h; while (p->next != h) { if (p->next == pos) { break; } p = p->next; } if (p->next == h) { return; } ListNode* newnode = LTcreat(x); ListNode* pr = p->next; newnode->next = pr; newnode->prev = p; p->next = newnode; pr->prev = newnode; }

细讲：核心功能是 在指定节点 pos 的前驱位置插入新节点（即“在 pos 前面插入”）。

3.双向链表指定位置删除

删除节点需修改 前驱节点的 next 和 后继节点的 prev，并释放被删节点内存。关键是 处理边界情况（如 pos 是头/尾节点）。

函数形式：

void LTErase(ListNode* pos)

实现：

void LTErase(ListNode* pos) { assert(pos); ListNode* p = pos->prev; p->next = pos->next; pos->next->prev = p; free(pos); pos = NULL; }

细讲：步骤：通过 pos->prev 获取前驱节点 p；调整指针：p->next = pos->next（切断 p 与 pos 的连接，指向 pos 的后继）；调整后继节点的前驱指针：pos->next->prev = p（切断后继与 pos 的连接，指向 p）；释放 pos 节点内存，并置空局部指针 pos。前置断言 assert(pos)作用：确保 pos 不为空指针，避免后续 pos->prev 等操作引发崩溃。

4.总代码展示：(加入了测试代码)

1.h

#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int type; typedef struct ListNode { type data; //前驱指针,指向前一个指针 struct ListNode* prev; //后继指针，指向后一个指针 struct ListNode* next; }ListNode; void LTInit(ListNode** h); void LTPushBack(ListNode* h, type x); ListNode* LTcreat(type x); void LTPushFront(ListNode* h, type x); void LTPopBack(ListNode* h); void LTPopFront(ListNode* h); void LTDestory(ListNode* h); void print(ListNode* h); ListNode* LTFind(ListNode* h, type x); void LTInsert(ListNode* pos, type x); void LTInsertfront(ListNode* h,ListNode* pos, type x); void LTErase(ListNode* pos);

1.cpp

#include"1.h" void LTInit(ListNode** h) { ListNode* ph = (ListNode*)malloc(sizeof(ListNode)); if (ph == NULL) { perror("malloc fail!"); exit(1); } *h = ph; (*h)->data = -1; (*h)->next = *h; (*h)->prev = *h; } ListNode* LTcreat(type x) { ListNode* ph = (ListNode*)malloc(sizeof(ListNode)); if (ph == NULL) { perror("malloc fail!"); exit(1); } ph->data = x; ph->next = ph; ph->prev = ph; return ph; } void LTPushBack(ListNode* h, type x) { ListNode* p = LTcreat(x); p->next = h; p->prev = h->prev; h->prev->next = p; h->prev = p; } void LTPushFront(ListNode* h, type x) { ListNode* p = LTcreat(x); p->next = h->next; p->prev = h; h->next->prev = p; h->next = p; } bool LTEmpty(ListNode* phead) { assert(phead); return phead->next == phead; } void LTPopBack(ListNode* h) { if (LTEmpty(h)) { return; } ListNode* p = h->prev; h->prev = p->prev; p->prev->next = h; free(p); } void LTPopFront(ListNode* h) { if (LTEmpty(h) ) { printf("链表为空，无法头删\n"); return; } ListNode* p = h->next; h->next = p->next; p->next->prev = h; free(p); } void LTDestory(ListNode* h) { if (LTEmpty(h)) { free(h); return; } ListNode* p = h->next; while (p != h) { ListNode* pr = p; p = p->next; free(pr); } free(h); h = NULL; } void print(ListNode* h) { if (LTEmpty(h)) { return; } ListNode* p = h->next; while (p != h) { printf("%d ", p->data); p = p->next; } printf("\n"); } ListNode* LTFind(ListNode* h, type x) { if (LTEmpty(h)) { return NULL; } ListNode* p = h->next; while (p != h) { if (p->data == x) { return p; } p = p->next; } return NULL; } void LTInsert(ListNode* pos, type x) { assert(pos); ListNode* p = pos->next; ListNode* newnode = LTcreat(x); pos->next = newnode; newnode->prev = pos; newnode->next = p; p->prev = newnode; } void LTInsertfront(ListNode* h, ListNode* pos, type x) { if (LTEmpty(h)) { return ; } ListNode* p = h; while (p->next != h) { if (p->next == pos) { break; } p = p->next; } if (p->next == h) { return; } ListNode* newnode = LTcreat(x); ListNode* pr = p->next; newnode->next = pr; newnode->prev = p; p->next = newnode; pr->prev = newnode; } void LTErase(ListNode* pos) { assert(pos); ListNode* p = pos->prev; p->next = pos->next; pos->next->prev = p; free(pos); pos = NULL; }

main.cpp

#include"1.h" void test() { ListNode* h; LTInit(&h); LTPushBack(h, 10); //10 LTPushBack(h, 15); //10 15 LTPushBack(h, 111); //10 15 111 print(h); LTPushFront(h, 2); //2 10 15 111 LTPushFront(h, 12); //12 2 10 15 111 print(h); LTPopBack(h); // 12 2 10 15 print(h); LTPopFront(h); //2 10 15 print(h); ListNode* p = LTFind(h,10); LTInsert(p, 100); //2 10 100 15 print(h); LTInsert(p, 200); //2 10 200 100 15 print(h); LTErase(p); print(h); //2 200 100 15 LTDestory(h); } int main() { test(); }

二、顺序表与链表的分析

本图列举了顺序表与链表之间的相同点与不同点：

一、相同点逻辑结构一致：均为线性表，数据元素之间呈一对一的顺序关系。核心操作相同：都支持插入、删除、查找、遍历等基本线性表操作。存储数据类型：均可存储相同类型的数据元素（如整数、结构体等）。二、不同点（核心差异）三、关键结论顺序表：适合 频繁随机访问、数据量固定 的场景（如存储学生信息表）。链表：适合 频繁插入删除、数据量动态变化 的场景（如实现队列、栈）。

三、链表算法题

一、移除链表元素

移除链表元素

203. 移除链表元素 - 力扣（LeetCode）

由题意可知，本题要求移除值为val的节点，并要求返回新的头结点：1.链表的解法可以通过遍历整个链表，用一个节点存储前一个节点，在发现值为val时候改变next区域的指向解答：2.我们也可以选择创建一个新链表，存储符合要求的节点，虽然没有释放原链表空间，但做OJ题不释放也没什么问题的，该方法较为简单，本次解题选择此方法：

解题代码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode Node; struct ListNode* removeElements(struct ListNode* head, int val) { Node *h=NULL,*pr=NULL; Node * p=head; while(p) { if(p->val!=val) { if(h==NULL) { h=p; pr=p; } else { pr->next=p; pr=p; } } p=p->next; } if(pr) pr->next=NULL; return h; }

解题思路：

1.变量初始化h：新链表的头节点，初始为 NULL（表示新链表为空）。pr：新链表的尾节点指针，用于拼接有效节点（值不等于 val 的节点）。p：遍历指针，从原链表头节点 head 开始，依次访问每个节点。

2. 遍历原链表（while (p)）

循环条件 p 等价于 p != NULL，即遍历至原链表末尾时停止。情况1：当前节点 p 的值不等于 val（需保留）首次保留节点（h == NULL）：
新链表为空，因此 h（头节点）和 pr（尾节点）都指向当前节点 p。非首次保留节点（h != NULL）：
通过 pr->next = p 将当前节点 p 拼接到新链表尾部，然后 pr = p 更新尾节点指针。情况2：当前节点 p 的值等于 val（需删除）
不执行任何操作（不拼接至新链表），直接通过 p = p->next 跳过当前节点。

3. 处理新链表尾节点（if (pr) pr->next = NULL）遍历结束后，pr 指向新链表的最后一个有效节点。若新链表非空（pr != NULL），需将其 next 置为 NULL，避免原链表中后续节点（已删除节点）的指针残留，导致野指针风险。

4. 返回新链表头节点

h 指向新链表的第一个有效节点，若原链表所有节点都被删除（如 head = [2,2,2], val=2），则 h 保持 NULL，返回空链表。

二、反转链表

反转链表

206. 反转链表 - 力扣（LeetCode）

解题思路:

反转题中给出的链表，如果简单来想，我们可以创建一个新链表一个一个节点的复制，但是题中的是单链表，不可找到前驱节点的，如果用上面思路，那会相当麻烦了。正确思路：通过三个指针来实现：迭代法（推荐：时间O(n)，空间O(1)）核心思路：通过 3个指针 遍历链表，逐次反转节点指向：prev：指向 已反转部分 的头节点（初始为 NULL）。curr：指向 当前待反转节点（初始为 head）。next：临时保存 curr 的下一个节点（避免反转后断链）。

简单来做，我将其命名为s1,s2,s3了。

基本结构是这样的，接下来我将结合代码来讲解:

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode node; struct ListNode* reverseList(struct ListNode* head) { node * s1=NULL; node *s2=head,*s3=NULL; if(s2) { s3=s2->next; } while(s2) { s2->next=s1; s1=s2; s2=s3; if(s3) { s3=s3->next; } } return s1; }

讲解：

图示：

根据上图：我们可知代码 if (s3) { s3 = s3->next; 的原因了：

while (s2) { // 循环条件：当前待反转节点 s2 不为 NULL（遍历完所有节点后终止）
// 步骤1：反转当前节点 s2 的指向（指向已反转部分的头节点 s1）
s2->next = s1;
// 步骤2：s1 后移到 s2（已反转部分的长度+1，s1 成为新的“已反转头节点”）
s1 = s2;
// 步骤3：s2 后移到 s3（继续处理下一个待反转节点）
s2 = s3;
// 步骤4：若 s3 不为空，s3 后移到下一个节点（为下次循环做准备）
if (s3) {
s3 = s3->next;
}
}
return s1; // 循环结束后，s1 指向原链表的尾节点（即新链表的头节点）