链表相关操作

 1 #include <iostream>
 2 using namespace std;
 3 typedef struct list
 4 {
 5     int data;
 6     struct list* next;
 7     list():data(0),next(NULL){}
 8 }List;
 9 
10 //1. 后插法插入数据
11 void insertData(List *p, int data)
12 {
13     if (p == NULL)
14         return;
15 
16     //申请空间
17     List *tmp = (List *)malloc(sizeof(List));
18     tmp->data = data;
19     tmp->next = NULL;
20 
21     //插入链表
22     while (p->next != NULL)
23         p = p->next;
24     p->next = tmp;
25 }
26 //2. 打印数据
27 void printData(List *p)
28 {
29     while (p != NULL)
30     {
31         cout << p->data << endl;
32         p = p->next;
33     }
34 }
35 
36 //3.链表逆序1
37 /*******************************************
38 三个指针，pre,cur,next
39 先保存cur的next到next中；
40 然后cur->next指向前面的；
41 pre和cur向前推进，next只是临时存储cur->next
42 *******************************************/
43 List* revertList(List *p)
44 {
45     List *pre  = nullptr;
46     List *next = nullptr;
47     while (p != nullptr)
48     {
49         next = p->next;
50         p->next = pre;
51         pre = p;
52         p = next;
53     }
54     return pre;
55 }
56 //4.链表逆序2
57 /***********************************
58 将链表看成两个结点，头结点和后面整体
59 ***********************************/
60 List* revertList2(List *p)
61 {
62     List *newphead;
63     if ((p == NULL) || (p->next == NULL))
64         return p;
65     newphead = revertList2(p->next);
66     p->next->next = p;
67     p->next = NULL;
68     return newphead;
69 }
70 
71 
72 int main()
73 {
74     List *phead = new List;
75     for (int i = 0; i < 20; i++)
76     {
77         insertData(phead, i);
78     }
79 
80     printData(phead);
81 
82     phead=revertList(phead);
83 
84     printData(phead);
85     cout << "AAAAAAAAAAAAA" << endl;
86     phead = revertList2(phead);
87 
88     printData(phead);
89 
90 
91     return system("pause");
92 }