关于港口码头发展建设的网站,自媒体平台注册,网页小游戏代码,wordpress centos设计一个算法#xff0c;将链表中所有结点的链接方向“原地”逆转#xff0c;即要求仅利用原表的存储空间#xff0c;换句话说#xff0c;要求算法的空间复杂度为O#xff08;1#xff09;
代码思路#xff1a; 这里要求不用额外空间#xff0c;那么就要考虑链表自身的…设计一个算法将链表中所有结点的链接方向“原地”逆转即要求仅利用原表的存储空间换句话说要求算法的空间复杂度为O1
代码思路 这里要求不用额外空间那么就要考虑链表自身的性质了。我们可以先让指针p指向链表L首元素然后把链表L整个断开也就是说此时L是空链然后依次把p指向的元素向L中头插即可。 头插会形成逆序
//将链表元素原地逆转带头结点
void NiZhuan(LinkList* L) {LNode* p (*L)-next;//用p继承一下L的元素(*L)-next NULL;//L元素清空//下面把p的元素进行头插即可完成逆序while (p ! NULL) {LNode* s (LNode*)malloc(sizeof(LNode));s-next (*L)-next;s-data p-data;(*L)-next s;p p-next;}}
int main()
{LinkList L;InitList2(L);//初始化一个带头结点链表1,2,3,4,5,6,7,8,9,10printf(初始链表为);print2(L);printf(\n);NiZhuan(L);printf(逆转后的链表为);print2(L);return 0;
}ps链表初始化及打印函数
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includestdbool.h
#includemalloc.h
//单链表定义
//链表结点
int A[10] { 1,2,3,4,5,6,7,8,9,10 };
int B[6] { 4,7,8,9,11,13 };//4,7,8,9,11,13
typedef struct {//定义单链表结点类型int data;//数据域struct LNode *next;//指针域
}LNode, *LinkList;//带头结点初始化-尾插法
void InitList2(LinkList* L) {(*L) (LNode*)malloc(sizeof(LNode));(*L)-next NULL;LNode* rear (*L);//标记表尾int i 0;for (i 0;i 10;i) {LNode* p (LNode*)malloc(sizeof(LNode));//创建一个新结点p-data A[i];//新结点赋值rear-next p;//接到L上rear p;//标记表尾}rear-next NULL;
}void print2(LinkList L) {//打印带头结点的链表LNode* i L-next;//用i指针遍历整个链表while (i ! NULL) {printf(%d , i-data);i i-next;}
}
