2-6 链表逆序

2-6 链表逆序

我只介绍两种常用方法吧,非递归方法 和 递归 方法 我觉得够用就行

1、非递归方法:

第二个元素后面的元素依次插入到头结点后面,

最后再把原始第一个元素放到原始第二个元素后面,整个链表就能够反转了

这个方法对于带不带头结点的链表都适用:

①不带头结点

原始链表,其中第二个元素是 B

A -> B-> C -> D -> E -> F -> null

先进入循环,不断的把B的后继元素往第一个元素后面插

A -> C -> B -> D -> E -> F -> null #将上面 B后的C 插入到A后面

A -> D -> C -> B -> E -> F -> null #将上面 B后的 D 插入到A后面

A -> E -> D -> C -> B -> F -> null #将上面 B后的 E 插入到A后面

A -> F -> E -> D -> C -> B -> null #将上面 B后的 F 插入到A后面

最后将A放到B后面:

F -> E -> D -> C -> B -> A -> null

void Reverse(node **h) {
	if ((*h) == nullptr)
		return;
	else if ((*h)->next == nullptr)
		return;

	else {
		node *r=nullptr, *p1 = (*h), *p2 = (*h)->next;

		while (p2->next != nullptr) {
			//由于p2一直固定在原始的第2个元素
			//所以r一直都是取紧接着原始的第2个元素右侧的那个元素地址
			r = p2->next;
			p2->next = r->next;

			//将r插入到第1个元素后面,这里因为第1个元素的位置P1也不变,所以也很简单
			r->next = p1->next;
			p1->next = r;
		}
		//最后再来处理原始的第1个元素P1 和 原始的第2个元素P2的顺序
		p2->next = p1;
		(*h) =p1->next;
		p1->next = nullptr;
	}
}

②带头结点的链表

可以将头结点视为第一个元素,那么就是直接把 A 的后继元素不断的往head后面插:

带头结点原始链表,将头结点视为第1个元素,那么其中第2个元素是 A

Head -> A -> B -> C -> D -> E -> F -> null

先进入循环,不断的把A的后继元素往头结点后面插

Head -> B -> A -> C -> D -> E -> F -> null

Head -> C -> B -> A -> D -> E -> F -> null

Head -> D -> C -> B -> A -> E -> F -> null

Head -> E -> D -> C -> B -> A -> F -> null

Head -> F -> E -> D -> C -> B -> A -> null

只不过最后不用将第一个元素放到A后面,也就是不用修改头指针

void Reverse(node *h) {
	if (h->next == nullptr) {
		cout << "这是空表!" << endl;
		return;
	}
	else if (h->next->next == nullptr) {
		cout << "只有一个元素,无需反转!" << endl;
		return;
	}
	else {
		node *p2 = h->next;//将头结点视为第1个元素,那么数据首节点就视为第2个元素
		node *r;
		/*将第二个元素后面的元素依次插入第一个元素后面*/
		while (p2->next != nullptr) {
			//由于p2一直固定在原始的第2个元素
			//所以r一直都是取紧接着原始的第2个元素右侧的那个元素地址
			r = p2->next;
			p2->next = r->next;

			//将r插入到头结点后面
			r->next = h->next;
			h->next = r;
		}
		//最后与不带头结点的单链表的区别就是,不用修改头指针了

	}
}

2、递归方法

①不带头结点

递归其实就是一直要找到最后一个结点,然后每次改一下,

这个时候其实 函数递归的时,函数用栈存储了前面每个结点的信息,所以一步一步从最后面改动到前面去,图我也就不画了,

画起来麻烦,可以参考一下这个博文的图,https://blog.csdn.net/fx677588/article/details/72357389

node* ReverseList_Recursion(node *p) {

	/*结束的条件:链表为空或者链表最后一个节点*/
	if (p == nullptr || p->next == nullptr) {
		return p;
	}
	//递归调用
	node *NewHead = ReverseList_Recursion(p->next);

	//每次都把当前结点 重新设置成 当前结点的下一个结点的下一个结点
	p->next->next = p;
	//然后再把当前结点的新后继设置为空,相当于当前结点时新链表的尾结点
	p->next = nullptr;
	return NewHead;
}

要调用此函数的时候,假设已经存在单链表的头指针:list1_h;

直接:node * list_2 = ReverseList_Recursion( list1_h );

这样新的头指针list_2就是反转后的链表的头指针

②带头结点

其实依然可以用上面的函数,只是,

对于带头结点的链表,直接向上面那样 把 头结点的地址作为参数传递进去 是不行的!

因为头结点其实并不是数据元素,数据域的值是随机的,这样直接操作会把头结点最后当做逆序后的尾结点,

另外①中直接返回一个新的头指针,其实就是原来的尾结点的地址,这样一来①中的函数其实是返回了一个以原始尾结点的地址为头指针的 无头结点单链表!

所以我们改一下调用的那行代码,就可以拿来对带头结点的单链表 进行逆序操作了:

list2->next = ReverseList_DG(list2->next)

上面这行代码,是把带头结点的单链表的下一个元素,也就是数据首元素的地址传入了递归函数中!(其实带头结点的单链表不看头结点就是 一个不带头结点的单链表)

然后把返回的 新的地址,又接入到 头结点的后面!

这样就可以在不改变原来头结点 地址 的情况下, 仅对数据部分进行逆序啦。

若有错误,还请不吝指出,谢谢

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券