《数据结构教程》（李春葆 主编）课后习题笔记【2.4】

 1 void invert(LinkList *&head)    //逆置链表处理 
 2 {
 3     LinkList* p = head->next;
 4     LinkList* pri = NULL;    //之前的节点 
 5     while(p){
 6         LinkList* q = new LinkList;
 7         q->data = p->data;    //把当前节点记录下来 
 8         q->next = pri;
 9         pri = q;
10         head->next = q;
11         LinkList* t = p;    //当前节点没用了删除掉 
12         p=p->next;
13         delete(t);
14     }
15 }

 1 //链表逆置
 2 //思路是遍历原链表，不断将当前节点以头插法插到head头节点后面，以此实现逆置 
 3 
 4 #include <iostream>
 5 using namespace std;
 6 #define Max 10 
 7 struct LinkList{
 8     int data;
 9     LinkList* next;
10 };
11 void CreateLinkList(int a[],int n,LinkList* &head)        //创建一个链表，把a数组中的数据依次放进去 
12 {
13     LinkList *p = head;
14     for(int i=0;i<n;i++){
15         LinkList *q = new LinkList;
16         q->data = a[i];
17         q->next = NULL;
18         p->next = q;
19         p = q;
20     }
21 }
22 void Display(LinkList *&head)    //输出链表 
23 {
24     LinkList *p = head->next;
25     while(p!=NULL){
26         cout<<p->data<<‘ ‘;
27         p=p->next;
28     }
29     cout<<endl;
30 }
31 void invert(LinkList *&head)    //逆置链表处理 
32 {
33     LinkList* p = head->next;
34     LinkList* pri = NULL;    //之前的节点 
35     while(p){
36         LinkList* q = new LinkList;
37         q->data = p->data;    //把当前节点记录下来 
38         q->next = pri;
39         pri = q;
40         head->next = q;
41         LinkList* t = p;    //当前节点没用了删除掉 
42         p=p->next;
43         delete(t);
44     }
45 }
46 int main()
47 {
48     int a[Max],n=Max;
49     for(int i=0;i<Max;i++)
50         a[i] = i+1;
51     LinkList *head = new LinkList;
52     CreateLinkList(a,n,head);    //将数组a中的元素顺序创建成一个链表 
53     Display(head);    //输出该链表 
54     invert(head);    //将该链表逆置处理 
55     Display(head);    //输出处理后的链表 
56     return 0;
57 }