1. 与408关联解析及本节内容介绍

1 本节内容介绍

本节分为四小节讲解。
第一小节是链表删除进行实战
第二小节是是针对408考研真题2019年41题进行题目解读与解题设计
第三小节是针对408考研真题2019年41题进行实战
第四小节是分析真题实战代码的时间复杂度

2. 单链表的删除操作实战

• 一切数据结构 - 增删查改

之前介绍了链表的新增、删除、查找的原理。

• 单链表删除操作流程图：

画流程图很关键。

单链表删除操作：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>typedef int ElemType; //写分号typedef struct LNode
{ElemType data; //数据域struct LNode* next;
}LNode, * LinkList;void list_tail_insert(LNode*& L)
{L = (LinkList)malloc(sizeof(LNode));//申请头结点空间，头指针指向头结点L->next = NULL;//头结点的next为NULLElemType x;scanf("%d", &x);LNode* s, * r = L;//s用来指向申请的新节点，r始终指向列表尾部while (x != 9999){s = (LinkList)malloc(sizeof(LNode));//为新节点申请空间s->data = x;r->next = s;//新节点给尾节点的next指针r = s;//r要指向新的尾部scanf("%d", &x);}r->next = NULL;//让尾节点的next为NULL
}void print_list(LinkList L)
{L = L->next;while (L != NULL){printf("%3d", L->data);L = L->next;}printf("\\n");
}
//按位置查找
LinkList GetElem(LinkList L, int SearchPos)
{int j = 0;if (SearchPos < 0){return NULL;}while (L && j < SearchPos)//L!=NULL，地址不为NULL{L = L->next;j++;}return L;
}//删除第i个位置的元素
//删除时不改变L，所以不需要加引用
bool ListDelete(LinkList L, int i)
{LinkList p = GetElem(L, i - 1);//拿到要删除结点的前一个结点指针p//判断p是不是空的if (NULL == p){return false;}LinkList q = p->next;//拿到p的下一个结点指针 - 即要删除的结点指针p->next = q->next;//断链free(q);//释放return true;
}//尾插法新建链表
int main()
{LinkList L; //L是链表头指针，是结构体指针类型 - 大小8个字节//list_head_insert(L); //输入数据可以为3 4 5 6 7 9999，头插法新建链表list_tail_insert(L);print_list(L); //链表打印ListDelete(L, 4);//删除第四个结点print_list(L);return 0;
}

这里删除第四个结点，运行结果为：

3. 单链表真题解读与解题设计

1 题目解读

2019年(单链表)
41.(13分)设线性表L=(a1,a2,a3,…,an−2.an−1,an)L=(a_1,a_2,a_3,…,a_{n-2}.a_{n-1},a_n)L=(a1​,a2​,a3​,…,an−2​.an−1​,an​)采用带头结点的单链表保存，链表中的结点定义如下：

	typedef struct node {int data;struct node* next;} NODE;

        请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L′=(a1,an,a2,an−1,a3,an−2…)L'=(a_1,a_n,a_2,a_{n-1},a_3,a_{n-2}…)L′=(a1​,an​,a2​,an−1​,a3​,an−2​…)。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
（3）说明你所设计的算法的时间复杂度。

解读:
首先空间复杂度是O(1)，不能申请额外的空间，然后找到链表的中间结点，前面一半是链表L，将链表的后半部分给一个新的头结点L2，然后将链表L2进行原地逆置，然后再将L和L2链表进行交替合并。

空间复杂度O(?)：额外使用的空间和原有空间之间的比例关系。

2 解题设计

分解题目，针对三个阶段封装三个子函数，条理清晰、逻辑缜密。

第一阶段：双指针找中间结点

如何找到链表的中间结点。

1. 方法一：首先遍历一次链表，长度假如是20，再次遍历走到第10个。
   这样的缺点是遍历了两次链表。
   不好。
2. 方法二：两个指针同步向后遍历的方法。
   定义两个指针pcur，ppre，让pcur指针每次走两步，ppre指针每次走一步，这样当pcur 指针走到最后，那么ppre指针刚好在中间。
   好。

注意，由于pcur每次循环是走两步的，因此每走一步都注意判断是否为NULL。

双指针找中间结点：

第二阶段：原地逆置

后一半链表我们设置为了L2，如何让 L2原地逆置？
        首先需要判断链表是否为空，如果为空，就返回，如果只有1个结点，也不需要逆置，直接返回。
        第一步：链表原地逆置，需要使用3个指针，假如分别是r，s，t，它们分别指向链表的1,2,3,也就是前三个结点。
        第二步：让s->next = r，这样2号结点就指向了1号结点，完成了逆置。
        第三步：这时，r = s，s = t，t = t->next，通过这个操作，r,s,t分别指向了链表的2,3,4结点，这时回到第二步，循环往复，当t为NULL时，结束循环。
        第四步：循环结束时，t为NULL，这时s是最后一个结点，r是倒数第第二个结点，需要再次执行一下s->next = r。
        第五步：最后需要L2->next->next = NULL；因为原有链表的头结点变成链表最后一个结点，最后一个结点的next需要为NULL。这时让L2->next = s，因为s是原链表最后一个结点，完成了逆置后，就是第一个结点，因此链表头结点L2指向s。

第三阶段：轮流放入合并链表

将L与L2链表合并，合并时轮流放入一个结点。
        因为空间复杂度是O(1)，因此不申请新空间，但是依然需要3个指针（pcur,p,q），合并后的新链表让pcur指针始终指向新链表尾部，初始化为pcur = L->next，使用p指针始终指向链表L待放入的结点，初始化值为p = L->next，q指针始终指向链表L2待放入的结点，初始化值为q =L2->next。因为链表L的第一个结点不动，所以 p=p->next。
        开启循环while(p != NULL && q != NULL)，首先将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放入即可。

4. 代码实战

代码流程：先用尾插法新建一条链表，然后将链表拆分为两条，分别为L和L2，然后L2进行逆置，再把L和L2进行合并。

此处代码演示与上文一致，实际解题时须与题目一致。

代码实现：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>typedef int ElemType; //写分号typedef struct LNode
{ElemType data; //数据域struct LNode* next;
}LNode, * LinkList;//尾插法新建链表
void list_tail_insert(LNode*& L)
{L = (LinkList)malloc(sizeof(LNode));//申请头结点空间，头指针指向头结点L->next = NULL;//头结点的next为NULLElemType x;scanf("%d", &x);LNode* s, * r = L;//s用来指向申请的新节点，r始终指向列表尾部while (x != 9999){s = (LinkList)malloc(sizeof(LNode));//为新节点申请空间s->data = x;r->next = s;//新节点给尾节点的next指针r = s;//r要指向新的尾部scanf("%d", &x);}r->next = NULL;//让尾节点的next为NULL
}//打印链表
void print_list(LinkList L)
{L = L->next;while (L != NULL)//NULL时为了代表一张空的藏宝图{printf("%3d", L->data);//打印当前结点数据L = L->next;//指向下一个结点}printf("\\n");
}//找到链表中间结点，并设置好L2链表
void find_middle(LinkList L, LinkList &L2)
{L2 = (LinkList)malloc(sizeof(LNode));//第二条链表的头结点LinkList pcur, ppre;//双指针遍历 - 常考！ppre = pcur = L->next;while (pcur){pcur = pcur->next;//要检验每一步后是否结束，所以不可以写成pcur = pcur->next->next！if (NULL == pcur)//为了防止pcur为NULL{break;}pcur = pcur->next;//判断没有结束，再走一步if (NULL == pcur)//前一个指针在第二步结束时，后一个指针不动{break;}ppre = ppre->next;}L2->next = ppre->next;//由L2头结点指向后面一半链表 - 让L2成为后一半ppre->next = NULL;//前一半链表的最后一个结点的next为NULL - 让L成为前一半
}//原地逆置链表
void reverse(LinkList L2)//不改变头指针L2，不需要加引用&
{LinkList r, s, t;r = L2->next;if (NULL == r){return;//链表为空 - 只有头结点}s = r->next;if (NULL == s){return;//链表只有1个结点}t = s->next;while (t)//t不为空{s->next = r;//原地逆置r = s;//以下3句 - 3个指针同时向后走一步s = t;t = t->next;}s->next = r;L2->next->next = NULL;//逆置后，链表第一个结点的next要为NULLL2->next = s;//s时链表第一个结点，L2指向它
}//轮流放入合并链表
void merge(LinkList L, LinkList L2)
{LinkList pcur, p, q;pcur = L->next;//pcur始终指向合并链表的链表尾p = pcur->next;//p指向L链表第一个结点 - p用来遍历L链表q = L2->next;//q指向L2链表第一个结点 - q用来遍历L2链表while (NULL != p && NULL != q){pcur->next = q;//链表L2给过来一个结点q = q->next;//指向下一个pcur = pcur->next;//合并链表往后走一个pcur->next = p;//链表L给过来一个结点p = p->next;//指向下一个pcur = pcur->next;//合并链表往后走一个}//任何一个链表都可能剩余一个结点，放进来即可if (NULL != p){pcur->next = p;}if (NULL != q){pcur->next = q;}
}int main()
{LinkList L; //链表头，是结构体指针类型list_tail_insert(L);print_list(L); //链表打印//寻找中间结点，并返回第二条链表LinkList L2 = NULL;find_middle(L, L2);//只有一个结点时，L2中是没有结点的printf("-----------------------------\\n");//双指针遍历 - 分L和L2链表print_list(L);print_list(L2);printf("-----------------------------\\n");//原地逆置链表reverse(L2);print_list(L2);printf("-----------------------------\\n");//轮流放入合并链表merge(L, L2);free(L2);print_list(L);return 0;
}

输入偶数个：1 2 3 4 5 6 9999
输出结果为：

输入奇数个：1 2 3 4 5 6 7 9999
输出结果为：

5. 时间复杂度分析

分析上一部分代码。

第一部分：find_middle函数，可以看到有一个while循环，因为pcur每次移动两个节点，因此循环的次数是n/2，忽略首项系数，所以时间复杂度是O(n)

//找到链表中间结点，并设置好L2链表
void find_middle(LinkList L, LinkList &L2)
{L2 = (LinkList)malloc(sizeof(LNode));//第二条链表的头结点LinkList pcur, ppre;//双指针遍历 - 常考！ppre = pcur = L->next;while (pcur){pcur = pcur->next;//要检验每一步后是否结束，所以不可以写成pcur = pcur->next->next！if (NULL == pcur)//为了防止pcur为NULL{break;}pcur = pcur->next;//判断没有结束，再走一步if (NULL == pcur)//前一个指针在第二步结束时，后一个指针不动{break;}ppre = ppre->next;}L2->next = ppre->next;//由L2头结点指向后面一半链表 - 让L2成为后一半ppre->next = NULL;//前一半链表的最后一个结点的next为NULL - 让L成为前一半
}

第二部分：reverse函数，遍历了L2链表，遍历长度是n/2，所以时间复杂度是O(n)

//原地逆置链表
void reverse(LinkList L2)//不改变头指针L2，不需要加引用&
{LinkList r, s, t;r = L2->next;if (NULL == r){return;//链表为空 - 只有头结点}s = r->next;if (NULL == s){return;//链表只有1个结点}t = s->next;while (t)//t不为空{s->next = r;//原地逆置r = s;//以下3句 - 3个指针同时向后走一步s = t;t = t->next;}s->next = r;L2->next->next = NULL;//逆置后，链表第一个结点的next要为NULLL2->next = s;//s时链表第一个结点，L2指向它
}

第三部分：merge函数，while循环遍历次数也是n/2，因此时间复杂度是O(n)

//轮流放入合并链表
void merge(LinkList L, LinkList L2)
{LinkList pcur, p, q;pcur = L->next;//pcur始终指向合并链表的链表尾p = pcur->next;//p指向L链表第一个结点 - p用来遍历L链表q = L2->next;//q指向L2链表第一个结点 - q用来遍历L2链表while (NULL != p && NULL != q){pcur->next = q;//链表L2给过来一个结点q = q->next;//指向下一个pcur = pcur->next;//合并链表往后走一个pcur->next = p;//链表L给过来一个结点p = p->next;//指向下一个pcur = pcur->next;//合并链表往后走一个}//任何一个链表都可能剩余一个结点，放进来即可if (NULL != p){pcur->next = p;}if (NULL != q){pcur->next = q;}
}

上面3个函数总的运行次数是1.5n，忽略首项系数，因此时间复杂度是O(n)

总结

2

• 单链表删除操作流程图：

3.2

• 两个指针同步向后遍历的方法很常用

5

• 分析时间复杂度时最好分块分析
• 时间复杂度忽略首项系数