编程之美读书笔记---单链表反序---要求只遍历一次

扩展问题：

编写一个函数，给定一个链表的头指针，要求只遍历一次，将单链表中的元素顺序反序。

 

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
struct node{
	int data;
	node *next;
};
void reverselist(node* &head)
{
	node *p,*q;
	p=head->next;
	q=head->next->next;
	if(q==NULL)return;  //若链表只有一个元素，则不操作 
	p->next=NULL;
	while(q->next!=NULL)
	{
		node *tmp=q->next;
		q->next=p;
		p=q;
		q=tmp;
	
	}
	q->next=p;
	head->next=q; //将表头指针调转 
}
void destroy(node* &head)
{
	node *p=head;
	head=head->next;
	while(head->next!=NULL)
	{
		delete p;
		p=head;
		head=head->next;
	}
	delete p;
	delete head;
} 
int main()
{
	node *head=new node;
	head->next=NULL;
	int n;
	cin>>n;
	while(n--)
	{
		
		node *pt=new node;
		cin>>pt->data;
		pt->next=head->next;
		head->next=pt;
	}
	reverselist(head); //此时简历的链表是输入的逆序，所以倒序后成为输入的正序 
	
	node *pt=head->next;
	while(pt->next!=NULL)
	{
		cout<<pt->data<<" ";
		pt=pt->next;
	}
	cout<<pt->data<<endl;
	destroy(head);      //记得资源回收 
	return 0;
}