单链表倒置(顺序与递归)

前端之家收集整理的这篇文章主要介绍了单链表倒置(顺序与递归)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

单链表倒置,给你一个头指针,用递归与非递归的方法分别实现;

分析见代码

代码如下:

//  [9/30/2013 qingezha] 链表倒置 循环与递归形式
//	一般形式,1—>2->3->4 现在1<-2<-3<-4  那么改变1的next的时候需要保存指向2的指针,然后同理处理2
//	需要保存的,用直译(见词知意)的表达出来比如:pre前面,next后面,cur当前,然后循环后赋新值
LinkPtrs reverse_link(LinkPtrs root) //头指针指向的是第一个元素
{
	if(root == NULL)
		return NULL;
	LinkPtrs nextp = root->next;		//第一个结点
	LinkPtrs pre = root;			//保留前端
	LinkPtrs temp = NULL;
	LinkPtrs reverseHead = NULL;
	pre -> next = NULL;
	while(nextp->next)
	{
		temp = nextp -> next;		//先要保存下一个指针
		nextp -> next = pre;
		pre = nextp;
		nextp = temp;
	}
	nextp -> next = pre;
	reverseHead = nextp;
	return reverseHead;
}
//链表倒置,切记 方法很巧!!!!!!!!!!!!!!!!!!
LinkPtrs reverse_link_recursive(LinkPtrs root)
{
	if(root == NULL)
		return NULL;
	LinkPtrs cur,temp,revers_head;
	if(root->next == NULL)
		return root;			//链表如果只有一个结点,那么直接返回第一个
	else
	{
		cur = root;
		temp = cur -> next;		//temp 为2->3->4的头指针
		//可以认为后面的都已经倒过来了,且认为revers_head 为倒过来的链表的头指针
		//这样理解就容易多了
		revers_head = reverse_link_recursive(temp);
		temp -> next = cur;
		cur -> next = NULL;
	}
	return revers_head;
}
原文链接:https://www.f2er.com/javaschema/285974.html

猜你在找的设计模式相关文章