江
江小南
V1
2022/12/07阅读：21主题：萌绿
【408篇】C语言笔记-第十二章（单链表的删除&考研真题实战）
第一节：单链表删除操作
删除操作流程图：
通过流程图，我们写出代码：
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode* next;
}LNode,*Linklist;
// 尾插法新建链表
Linklist list_tail_insert(Linklist &L){
int x;
L= (Linklist)malloc(sizeof(LNode)); // 带头结点的链表
LNode *s,*r=L; // 写成LinkList s,r=L;也可以。r代表链表表尾结点，指向链表尾部
scanf("%d",&x);
while (x!=9999){
s= (LNode*)malloc(sizeof(LNode));
s->data=x;
r->next=s; // 让r指针指向新的尾部
r=s; // 让r本身指向新的尾部
scanf("%d",&x);
}
r->next=NULL; // 尾结点的next指针赋值为NULL
return L;
}
// 按序号查找结点值
Linklist GetElem(Linklist L,int i){
int j=0;
if(i<0){
return NULL;
}
while (L && j<i){
L=L->next;
j++;
}
return L;
}
// 删除某个位置元素
bool ListDelete(Linklist L,ElemType i){
Linklist p=GetElem(L,i-1);
if(NULL==p){
return false;
}
Linklist q; // 用来存储要删除的节点地址
q=p->next;
p->next=q->next; // 断链
free(q); // 释放空间
return true;
}
// 打印链表中每个结点的值
void print_list(Linklist L){
L=L->next; // 头结点指向第一个指针
while (L!=NULL){
printf("%3d",L->data);
L=L->next; // 指向下一个指针
}
printf("\n");
}
int main() {
Linklist L,search; // L仅表示链表头，是结构体指针类型
list_tail_insert(L);
print_list(L); // 打印链表
ListDelete(L,4); // 删除第4个位置元素
print_list(L);
return 0;
}
F:\Computer\Project\practice\12\12.1-head-insert\cmake-build-debug\11_1_head_insert.exe
1 2 3 4 5 9999
1 2 3 4 5
1 2 3 5
进程已结束，退出代码为 0
对于删除元素的逻辑，可以用一张图来表示：
分析：
-
头指针的数据域始终为空，位置不动。 -
删除第i个元素实际上是将原本i元素的next赋值给i-1个位置元素的next。也叫作断链。这样第i-1个元素就和第i+1个元素链接起来，形成链表。 -
将要删除的元素地址保存起来，并做释放空间处理。
第二节：考研真题
解读：
-
空间复杂度为O(1)，即不能额外申请空间。 -
找到链表的中间结点，前面一半是链表L，将链表的后半部分给一个新的头结点L2，然后将链表L2原地逆置。 -
将L和逆置后的L2链表按照L'进行合并。
1. 解题设计
第一阶段：如何找到链表的中间结点？
定义两个指针pcur和ppre，让pcur指针每次走两步，ppre指针每次走一步，这样当pcur指针走到最后，那么ppre指针刚好在中间。指针p每次循环走两步，因此每一步都要注意判断是否为NULL。
第二阶段：后一半链表设置为了L2，如何让L2原地逆置？
首先我们要判断链表是否为空，如果为空，就返回。如果只有一个结点，也不需要逆置，直接返回。
-
链表原地逆置，我们需要使用3个指针，分别为r,s,t，他们分别指向链表的1,2,3的位置，也就是前3个结点。 -
让s->next=r，这样2号结点就指向了1号结点，完成了逆置。 -
这是，r=s,s=t,t=t->next，通过这个操作，r,s,t分别指向了链表的2,3,4位置结点。在循环执行第2步。当t为NULL时，结束循环。 -
循环结束时，t为NULL，这是s是最后一个结点，r是倒数第二个结点，需要再执行一次s->next=r。 -
最后需要L2->next->next=NULL;因为原有链表的头结点变成了链表的最后一个结点，最后一个结点的next需要为NULL，这时让L2指向s，因为s是原链表最后一个结点，完成逆置后，就是第一个节点，因此链表头结点L2指向s。
第三阶段：将L和L2链表合并，合并时轮流放入一个结点。
我们依然需要3个指针，pcur,p,q，让pcur始终指向新链表尾部，初始化为pcur=L->next。使用p指针始终指向链表L待放入的节点，初始化为p=L->next(因为L的第一个结点就是新链表的第一个结点)。q始终指向L2待放入的节点，初始化为q=L2->next。
开启循环，while(NULL!=p&&NULL!=q)，首先将pcur->next=q，然后q=q->next和pcur=pcur->next，接着pcur->next=p，然后p=p->next和pcur=pcur->next。直到循环结束。循环结束后，有可能L还剩余一个结点，也可能L2还剩余一个结点，但是只会有一个剩余的节点。判断p不为NULL，把p放入，如果q不为NULL，把q放入即可。
2. 代码实现
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode* next;
}LNode,*Linklist;
// 尾插法新建链表
Linklist list_tail_insert(Linklist &L){
int x;
L= (Linklist)malloc(sizeof(LNode)); // 带头结点的链表
LNode *s,*r=L; // 写成LinkList s,r=L;也可以。r代表链表表尾结点，指向链表尾部
scanf("%d",&x);
while (x!=9999){
s= (LNode*)malloc(sizeof(LNode));
s->data=x;
r->next=s; // 让r指针指向新的尾部
r=s; // 让r本身指向新的尾部
scanf("%d",&x);
}
r->next=NULL; // 尾结点的next指针赋值为NULL
return L;
}
// 寻找中间结点并返回第二个链表
void find_middle(Linklist L,Linklist &L2){
L2=(Linklist) malloc(sizeof(LNode));
Linklist pcur,ppre;
pcur=ppre=L->next; // 初始化双指针均为L的第一个结点
while (pcur!=NULL){
pcur=pcur->next; // pcur走第一步
if(NULL==pcur){
break;
}
pcur=pcur->next; // pcur走第二步
if(NULL==pcur){
break;
}
ppre=ppre->next; // ppre走一步
}
L2->next=ppre->next;
ppre->next=NULL;
}
// 原地逆转L2
void reverse(Linklist &L2){
Linklist r,s,t;
r=s=t=L2->next;
if(NULL==r){ // 链表为空
return;
}
s=t=t->next;
if(NULL==t){ // 链表只有一个结点
return;
}
t=t->next;
while (NULL!=t){
s->next=r;
r=s; // 三个节点依次向后移动
s=t;
t=t->next;
}
s->next=r;
L2->next->next=NULL; // 链表的第一个结点的next要为NULL
L2->next=s; // s是头部
}
// 合并链表
void merge(Linklist L,Linklist L2){
Linklist pcur,p,q;
pcur=p=L->next;
q=L2->next;
p=p->next;
while (q!=NULL && p!=NULL){
pcur->next=q; // 链表上给过来一个结点
q=q->next; // q往后走一步，q在L2上
pcur=pcur->next; // 新链表往后走一个
pcur->next=p; // 链表L2上给过来一个结点
p=p->next; // q往后走一步，它在L上
pcur=pcur->next; // 新链表往后走一步
}
if(NULL!=q){
pcur->next=q;
}
if(NULL!=p){
pcur->next=p;
}
}
// 打印链表中每个结点的值
void print_list(Linklist L){
L=L->next; // 头结点指向第一个指针
while (L!=NULL){
printf("%3d",L->data);
L=L->next; // 指向下一个指针
}
printf("\n");
}
int main() {
Linklist L,search; // L仅表示链表头，是结构体指针类型
list_tail_insert(L); // 尾插法新建列表
print_list(L); // 打印链表
Linklist L2=NULL; // 寻找中间结点并返回第二个链表
find_middle(L,L2);
printf("---------------------\n");
print_list(L);
print_list(L2);
printf("---------------------\n");
reverse(L2); // L2原地逆置
print_list(L2);
printf("---------------------\n");
merge(L,L2); // 重新合并链表
free(L2);
print_list(L);
return 0;
}
F:\Computer\Project\practice\12\12.2-head-insert\cmake-build-debug\11_1_head_insert.exe
1 2 3 4 5 6 7 8 9 9999
1 2 3 4 5 6 7 8 9
---------------------
1 2 3 4 5
6 7 8 9
---------------------
9 8 7 6
---------------------
1 9 2 8 3 7 4 6 5
进程已结束，退出代码为 0
3. 时间复杂度分析
find_middle函数有一个while循环，因为pcur每次移动两个结点，因为循环次数为n/2，忽略首项系数，时间复杂度为O(n)。
reverse函数值遍历了L2链表，遍历长度为n/2，所以时间复杂度为O(n)。
merge函数循环遍历次数也是n/2，因此时间复杂度为O(n)。
三个函数总的运行次数为1.5n，忽略首项系数，因此时间复杂度为O(n)。
作者介绍
江
江小南
V1