首页 > 代码库 > 算法题:反转单链表

算法题:反转单链表

说明:本文仅供学习交流,转载请标明出处,欢迎转载!

题目:存在一个单链表,头指针为head,实现单链表的反转Node *Reverse(Node *head)。 

         该算法的求解办法有很多,如:

          方法1:先顺序变量单链表,将结点保存到栈中,在从栈中弹出结点,重新建立一个新的单链表;

          方法2:用《剑指offer》里面给出的算法,用三个指针来实现;

          方法3:采用递归实现,是方法2的递归实现形式。

          本文主要给出方法2和方法3,在给出具体的代码之前,先要注意几个问题

         (1)如果head为空,该如何处理?

         (2)如果链表为单节点链表,该如何处理?

         (3)如何防止在反转过程中断链?

         (4)反转后head是否更新?

         (5)反转后得到的链表最后一个结点是否为null?

            考虑完以上问题后,就可以写出正确的代码了。

             代码实现如下:

<pre name="code" class="cpp">#include<iostream>
using namespace std;
struct Node
{
	int value;
	Node* next;
	Node(int v):value(v){}
};
/*创建一个链表,1->2->3->4->5->6->7*/
Node* CreateList()//创建一个单链表
{
   Node *head;
   Node *n1=new Node(1);
   Node *n2=new Node(2);
   Node *n3=new Node(3);
   Node *n4=new Node(4);
   Node *n5=new Node(5);
   Node *n6=new Node(6);
   Node *n7=new Node(7);
   head=n1;
   n1->next=n2;
   n2->next=n3;
   n3->next=n4;
   n4->next=n5;
   n5->next=n6;
   n6->next=n7;
   n7->next=NULL;
   return head;
}
void FreeList(Node *head)//将链表空间释放
{
	if(head==NULL)
	{
		return ;
	}
	else
	{
		Node *temp=head->next;
		delete head;
		head=temp;
		FreeList(head);
	}
}
void VisitList(Node *head)//遍历链表中的元素,用递归的方法遍历
{
	if(head)
	{
		cout<<head->value<<"->";
		VisitList(head->next);
	}
	else
	{
		cout<<"null"<<endl;
	}
}
Node *Reverse(Node *head)//反转单链表
{
	if(!head || !head->next)//如果是空链表或者仅含一个结点的链表
	{
		return head;
	}
	Node *p1,*p2,*temp;
	p1=head;
	p2=head->next;
	p1->next=NULL;//这是反正后链表的最后一个结点(即原来的第一个结点)
	while(p2)
	{
		temp=p2->next;//防止段链
		p2->next=p1;//反转
		//前进
		p1=p2;
		p2=temp;
	}
	head=p1;
	return p1;
}
Node *Reverse1(Node *head)//用递归法实现
{
	if(!head || !head->next)
	{
		return head;
	}
	Node *nextNode=head->next;
	head->next=NULL;
	Node *head1=Reverse(nextNode);
	nextNode->next=head;
	return head1;//这里是递归过程
}
int main()
{
	Node *head=CreateList();
	cout<<"原链表输出为:";
	VisitList(head);
	head=Reverse(head);
	cout<<"反转后的链表为(循环法):";//循环法
	VisitList(head);
	cout<<"再反转链表(递归法):";
	head=Reverse1(head);//递归法
	VisitList(head);
	FreeList(head);//释放链表空间
	return 0;
}

             测试结果如下:


  参考资料-------------《剑指offer》