单链表反转

一、单链表反转(非递归实现)

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 typedef struct _LinkList
 5 {
 6     int data;
 7     struct _LinkList *pnext;
 8 
 9 }LinkList;
10 
11 
12 LinkList *CreateList(LinkList *pHead, int array[], int n)
13 {
14     LinkList *q = pHead;
15     for(int i = 0; i < n; i++)
16     {
17         LinkList *p = (LinkList *)malloc(sizeof(LinkList));
18         p->pnext = NULL;
19         p->data = array[i];
20 
21         if(pHead->pnext == NULL)
22         {
23             pHead->pnext = p;
24             q = p;
25         }
26         else
27         {
28             q->pnext = p;
29             q = p;
30         }
31     }
32 
33     q = pHead;
34     pHead = pHead->pnext;
35     free(q);
36 
37     return pHead;
38 }
39 
40 LinkList *ReverseList(LinkList *pHead)
41 {
42     if(pHead == NULL || pHead->pnext == NULL)
43         return pHead;
44 
45     if(pHead->pnext->pnext == NULL)
46     {
47         LinkList *p = pHead->pnext;
48         pHead->pnext = NULL;
49         p->pnext = pHead;
50         return p;
51     }
52 
53     LinkList *p = pHead;
54     LinkList *q = p->pnext;
55     LinkList *r = q->pnext;
56 
57     while(r != NULL)
58     {
59         q->pnext = p;
60         p = q;
61         q = r;
62         r = r->pnext;
63     }
64 
65     q->pnext = p;
66     pHead->pnext = NULL;
67     pHead = q;
68 
69     return pHead;
70 }
71 
72 int main()
73 {
74     int array[] = {1, 2, 3, 4, 5, 6, 7, 8,9};
75 
76     LinkList *pHead = (LinkList *)malloc(sizeof(LinkList));
77     if(pHead == NULL)
78     {
79         printf("动态开辟空间失败！");
80         return 0;
81     }
82 
83     pHead->pnext = NULL;
84     pHead = CreateList(pHead, array, 3);
85 
86     pHead = ReverseList(pHead);
87 
88     LinkList *p = pHead;
89 
90     while(p != NULL)
91     {
92         printf("%d ", p->data);
93         p = p->pnext;
94     }
95     if(pHead != NULL)
96         printf("\n");
97 
98     return 0;
99 }

二、单链表反转(递归实现)

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 typedef struct _LinkList
 5 {
 6     int data;
 7     struct _LinkList *pnext;
 8 
 9 }LinkList;
10 
11 
12 LinkList *CreateList(LinkList *pHead, int array[], int n)
13 {
14     LinkList *q = pHead;
15     for(int i = 0; i < n; i++)
16     {
17         LinkList *p = (LinkList *)malloc(sizeof(LinkList));
18         p->pnext = NULL;
19         p->data = array[i];
20 
21         if(pHead->pnext == NULL)
22         {
23             pHead->pnext = p;
24             q = p;
25         }
26         else
27         {
28             q->pnext = p;
29             q = p;
30         }
31     }
32 
33     q = pHead;
34     pHead = pHead->pnext;
35     free(q);
36 
37     return pHead;
38 }
39 
40 LinkList *ReverseList(LinkList *pHead, LinkList *pre)
41 {
42     if(pHead == NULL)
43         return pHead;
44 
45     LinkList *p = pHead->pnext;
46     pHead->pnext = pre;
47 
48     if(p != NULL)
49         return ReverseList(p, pHead);
50     else
51         return pHead;
52 }
53 
54 int main()
55 {
56     int array[] = {1, 2, 3, 4, 5, 6, 7, 8,9};
57 
58     LinkList *pHead = (LinkList *)malloc(sizeof(LinkList));
59     if(pHead == NULL)
60     {
61         printf("动态开辟空间失败！");
62         return 0;
63     }
64 
65     pHead->pnext = NULL;
66     pHead = CreateList(pHead, array, 9);
67 
68     pHead = ReverseList(pHead, NULL);
69 
70     LinkList *p = pHead;
71 
72     while(p != NULL)
73     {
74         printf("%d ", p->data);
75         p = p->pnext;
76     }
77     if(pHead != NULL)
78         printf("\n");
79 
80     return 0;
81 }