目录

一. 整体思路

1-1-1.逆置函数的变量定义

1-1-2.求单链表表长，以及排除特殊情况

1-1-3.单链表的分段逆置核心代码

1-1-3-1.变量讲解

1-1-3-2.逻辑分析

---

一. 整体思路

单链表的分段逆置可以将单链表拆分成多个子单链表，我们将每一段分别逆置再相接，从而实现整体的分段逆置，关于单链表的逆置有多种方法，篇幅有限仅介绍两种，后续代码将围绕第一种方法讲解

1-1-1.逆置函数的变量定义

​
int n=0,i=0,j=0,num=0;
cin >> n;
LinkList p=L->next;
LinkList group_dummy=L;//每一组反转过的子单链表的尾结点都是下一段未反转过的子单链表的虚拟头结点 
LinkList group_tail; 
LinkList prev;
LinkList q;

​

1-1-2.求单链表表长，以及排除特殊情况

（1）若求出表长num/n<1即: 每段需逆置的结点数>单链表的长度，不成立，故结束函数

（2）若n<=1即：代表单链表每个结点都需要有一次逆置，但只有两个及以上的结点逆置单链表才与原先有区别，故不必更改单链表，后结束函数

while(p!=NULL)
{
	num++;
	p=p->next;
}
p=L->next;//记得遍历结束后p恢复原位 
if(num/n<1||n<=1)//排除临界条件的影响 
{
	return 0;	
}

1-1-3.单链表的分段逆置核心代码

1-1-3-1.变量讲解

 <1>  现将单链表划分成三段L1、L2、L3，分别代表已经逆置完成的部分（长度一定是n的倍数），正在逆置的部分（长度一定＜=n），未被逆置的部分（长度一定是n的倍数）

 <2>  prev是自定义的每个子单链表的最新逆置结点，相当于正在逆置的子单链表的首元结点

 <3>  group_tail是将准备逆置的子单链表（此时还未对其逆置）的第一个结点保存下来，逆置完成后不难发现此结点会成为当前子单链表的尾结点

 <4>  group_dummy是已经逆置完成部分的最后一个结点，将此结点作为未完成逆置部分的虚拟头结点

1-1-3-2.逻辑分析

 <1>  先将group_tail指向准备逆置的子单链表的第一个结点

 <2>  prev此时指向空结点，后续通过头插法接收反转后的结点

 <3>  内层循环是通过按顺序剥离L2未反转的结点，采取头插法再与L2已经反转后的结点相连，q的作用是保留L2中未反转部分的首结点，防止L2中p指向已反转部分后因单链表断裂导致的后续结点丢失，然后prev、p、q向后遍历

 <4>  此时L2已经逆置完成，但L2最开始与L1相连的首元结点此时为L2的尾结点，故L1与L2此时是断开的，所以将L1的尾结点（同时也可以视作L2的虚拟头结点）与L2逆置后的首元结点即此时prev所指向的结点相连，从而连接L1与L2

 <5>  因逆置后L2的尾结点变成L2的首元结点，所以L2与L3也是处于断开状态，此时q代表的就是L3的首元结点，故将group_tail指向p，从而连接L2与L3 <6>  因group_tail代表L2尾结点，此时L2的逆置完成，故L2会归与L1，新的L2从L3中取n个结点，故L2虚拟头结点group_dummy也应更新为group_tail，从而完成了L2虚拟头结点的更新

二.单链表

以下是单链表的初始化、尾插法、遍历输出，不做过多赘述

#include<iostream>
using namespace std;

typedef struct LNode
{
	int data;
	struct LNode *next;
}LNode, *LinkList;

void InitList(LinkList &L)
{
	L=new LNode;
	L->next=NULL;
}

int Creat(LinkList &L)
{
	int n,i=0;
	cin >> n;
	if(n==0)
	return 0;
	LinkList rear=L;
	for(i=0;i<n;i++)
	{
		LinkList p=new LNode;
		cin >> p->data;
		p->next=NULL;
		rear->next=p;
		rear=p;
	}
	return 1;
}
int Reversal(LinkList &L)//代码补充在这里

void Traverse(LinkList L)
{
	LinkList p=L->next;
	while(p!=NULL)
	{
		cout << p->data << " ";
		p=p->next;
	}
}

int main()
{
	LinkList L;
	InitList(L);
	if(Creat(L))
	{
		Reversal(L);
		Traverse(L);
	}
	return 0;
}