数据结构 -- 实现单链表的原地逆置_试写一算法,对单链表实现就地(原地)逆置。

题目：

        编写算法将一个单链表逆置；

分析：

        第一种方法：修改头指针；

        第二种方法：通过该表的*next指针实现：定义三个指针*p,*pre,*r，分别表示三个连续的结点；先用p->next=NULL断掉第一个结点的后继节点，用pre表示原来单链表中p的前驱结点，再用p->next指向pre，但同时p的后继结点会断开，所以需要用r来保存其后继结点。

功能函数代码：

画图理解：

        带头结点：

 

         不带头结点：

 完整代码（以带头结点为例）：

//原地逆置
typedef struct lnode
{
	int val;
	struct lnode* next;
}lnode, * linklist;
struct lnode* creatlist(int n)
{//创建链表
	linklist L = new lnode;
	L->next = NULL;
	cout << "请输入" << n << "个数：";
	for (int i = 0; i < n; i++) {	
		linklist p = new lnode;
		cin >> p->val;
		p->next = L->next;
		L->next = p;
			
	}
	return L;
}
void travelist(linklist& L)
{//打印链表
	linklist p = L->next;
	if (p == NULL) {
		cout << "该链表为空！" << endl;
		return;
	}
	while (p!=NULL) {
		cout << setw(6) << p->val;
		p = p->next;
	}
}
void reverse(linklist& L)
{//链表原地逆置函数
    //头插法
	linklist p;
	p=L->next;
	L->next = NULL;	//断开头结点
	while (p!=NULL) {
		linklist tem = p->next;	//保存p的后继结点
		p->next = L->next;		//断开p的后继节点
		L->next = p;			//p插入在头结点之后
		p = tem;				//p更新为下一个要继续插入的结点，即原链表的后继节点
	}
 
 
	//修改*next指针
	//linklist pre = NULL;
	//linklist cur = L->next;
	//while (cur != NULL) {
	//	linklist next = cur->next;
	//	cur->next = pre;
	//	pre = cur;
	//	cur = next;
	//}
	//L->next = pre;
 
	//修改*next指针的另一种写法
	//linklist pre = NULL, p = NULL, r = NULL;
	//r = L->next;
	//while (r != NULL)
	//{
	//	pre = p;
	//	p = r;
	//	r = r->next;
	//	p->next = pre;
	//}
	//L->next = p;
 
}
int main()
{//主函数
	int n;
	cout << "请输入链表的长度：";
	cin >> n;
	linklist L = new lnode;
	//linklist pre;
	L = creatlist(n);
	cout << "原链表为：  ";
	travelist(L);
	cout << endl;
	reverse(L);
	cout << "原地逆置后：";
	travelist(L);
	cout << endl;
}

 输出：

 参考了另一个博主的博客并做了些优化~

链接：https://blog.csdn.net/qq_40941722/article/details/94381637?utm_source=app&app_version=4.16.0https://blog.csdn.net/qq_40941722/article/details/94381637?utm_source=app&app_version=4.16.0