signed

QiShunwang

“诚信为本、客户至上”

链表反转的形象理解

2021/3/21 0:22:10   来源:

最近在学C语言,遇到一个问题: 怎么将一个链表反转并返回头部,且不能增加或删改内存?
在网上找了一下讲解,发现要么直接给代码。要么讲解的很抽象,放弃后自己仔细思考了一下,找到了一个效率不是很高但很容易理解的方法

总的来说是整体法,及先考虑两个节点反转,反转的结果看作一个整体,然后再与下一个节点反转,这样便可以进行循环,直到结尾指向NULL。

在刚开始考虑最简单的情况:

情况1
尝试将1,2节点反转。
很容易想到先将1的箭头指向3ph -> next = pt -> next;
得到:
在这里插入图片描述

然后将2的箭头指向1:ph -> next = head;
在这里插入图片描述

既然想将反转后的结果当作一个整体, 指针的位置应该相对不变, 使得可以继续往后反转:
在这里插入图片描述

把2, 1当作一个整体与3进行反转, 其指针位置应该与上面1, 2反转时相对差不多。
所以:head = pt; pt = ph -> next;

所以上面代码步骤为:

1.ph -> next = pt -> next;
2.ph -> next = head;
3.head = pt;
4.pt = ph -> next;

下面测试一下,重复以上代码,链表是否能一直反转。
初始时:
在这里插入图片描述

进行第一步:ph -> next = pt -> next;
可得:
在这里插入图片描述
进行第二步:ph -> next = head;
可得:
在这里插入图片描述
第三步:head = pt;
可得:
在这里插入图片描述
第四步:pt = ph -> next;
可得:
在这里插入图片描述
可以看出, 最后得到的结果依然与简单情况相统一的,循环可以继续下去。
最终结果是: head依然指向链表头,ph指向最后一个,pt指向NULL(循环一次时pt指向3)

所以可得完整代码:

struct node* reverse(struct node * head){//传进一个head指针
	//先放好初始指针(ph,pt)的位置
	struct node* ph = head -> next;
	struct node* pt = ph -> next;
	//下面进行循环操作
	while(pt != NULL){
		//进行上面的四个步骤即可
		ph -> next = pt -> next;
		ph -> next = head;
		head = pt;
		pt = ph -> next;
	}
	//反转结束后,反转头指针
	return head;
}

希望能帮到你