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

扩展问题：

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

#include #include #include #include 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<data<<" "; pt=pt->next; } cout<data< #include #include #include 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<data<<" "; pt=pt->next; } cout<data<