【23王道数据结构】链表课后题25，【2019统考真题】设线性表L=·······

思路：

时间复杂度 O(N) 空间复杂度O(1)

主要代码

void operate(LinkList &L) {if (L->next == NULL ||L->next->next == NULL ||L->next->next->next == NULL) return; //空链表，一个元素的链表，两个元素的链表不用操作int length = 0;LNode *p = L, *q; //q指向后半段的第一个元素 while (p->next) {length++;p = p->next;} int m = (1 + length) / 2; //用于确定q的位置p = L; //重定向Pwhile (m--) {p = p->next;} q = p->next; //找到位置p->next = NULL; //断开q及其以后节点invert(q); //逆置q，没有头结点； //奇数的话，第m个元素不用处理 m = (1 + length) >> 1;if (length % 2 != 0) m = m - 1;p = L;//将p指向头结点 for (int i = 0; i < m; i++) {p = p->next; //仔细思考 LNode *t = q;q = q->next; //对p执行后插 t->next = p->next;p->next = t;p = p->next;}}void invert(LinkList &L) {//构造头结点 LinkList Head; //头结点 Head = (LNode *)malloc(sizeof(LNode));Head->next = NULL;//逆置LNode *p = L; //这里L是无头结点的 while (p) {LNode *t = p;p = p->next;//头插 t->next = Head->next;Head->next = t;} //print(Head); L = Head->next; //将P指向第一个元素 //释放创建的头结点 free(Head); 
} 

全部代码

#include <iostream>
#include <stdlib.h>using namespace std;typedef struct LNode {int data;struct LNode *next;
}LNode, *LinkList;//尾插法
void TailInsert(LinkList &L); 
//遍历 
void print(LinkList L);void operate(LinkList &L); //无头结点的逆置 
void invert(LinkList &L); int main(void) {LinkList L;L = (LNode *)malloc(sizeof(LNode));L->next = NULL; //初始化 TailInsert(L);operate(L); cout << "main函数里:"; print(L);
} void print(LinkList L) {if (L->next == NULL) return;printf("链表中的元素如下:\n"); LNode *t = L->next; //指向第一个节点 while(t!= NULL) {printf("%d ",t->data);t = t->next;} printf("\n");
}void TailInsert(LinkList &L) {LNode *tail, *t;tail = L;int x;printf("请输入待插入的元素，以-1表示结束:\n"); scanf("%d",&x);while (x != -1) {t = (LNode*)malloc(sizeof(LNode));t->data = x;t->next = NULL;tail->next = t;tail = t;scanf("%d",&x);}
}
void operate(LinkList &L) {if (L->next == NULL ||L->next->next == NULL ||L->next->next->next == NULL) return; //空链表，一个元素的链表，两个元素的链表不用操作int length = 0;LNode *p = L, *q; //q指向后半段的第一个元素 while (p->next) {length++;p = p->next;} int m = (1 + length) / 2; //用于确定q的位置p = L; //重定向Pwhile (m--) {p = p->next;} q = p->next; //找到位置p->next = NULL; //断开q及其以后节点invert(q); //逆置q，没有头结点； //奇数的话，第m个元素不用处理 m = (1 + length) >> 1;if (length % 2 != 0) m = m - 1;p = L;//将p指向头结点 for (int i = 0; i < m; i++) {p = p->next; //仔细思考 LNode *t = q;q = q->next; //对p执行后插 t->next = p->next;p->next = t;p = p->next;}}void invert(LinkList &L) {//构造头结点 LinkList Head; //头结点 Head = (LNode *)malloc(sizeof(LNode));Head->next = NULL;//逆置LNode *p = L; //这里L是无头结点的 while (p) {LNode *t = p;p = p->next;//头插 t->next = Head->next;Head->next = t;} //print(Head); L = Head->next; //将P指向第一个元素 //释放创建的头结点 free(Head); 
}