链表相关操作

1 #include
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 <data <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" <86 phead = revertList2(phead);
87
88 printData(phead);
89
90
91 return system("pause");
92 }