无头单链表反转

  1 #include <iostream>                                                                                                 
  2 
  3 using namespace std;
  4 
  5 struct node
  6 {
  7     int data;
  8     node *next;
  9 };
 10 
 11 
 12 node *list_create(void)
 13 {
 14     node *head = NULL; 
 15     node **current = &head;
 16 
 17     cout << "input value until -1" << endl;
 18 
 19     int a = 0;
 20     cin >> a;
 21     while(a != -1)
 22     {
 23         *current = new node;
 24         (*current)->next = NULL; 
 25         (*current)->data = a;
 26         current = &((*current)->next);
 27         cin >> a;
 28     }
 29 
 30     return head;
 31 }
 32 
 33 void list_print(const node *head)
 34 {
 35 
 36     while(head)
 37     {
 38         cout << "node->next is : " << head->next << " node->data is : " << head->data <<endl; 
 39         head = head->next;
 40     }
 41 }
 42 
 43 node *node_delete(node *head, int data)
 44 {
 45     if(head == NULL)
 46         return head;
 47 
 48     node *current = head;
 49     node *prev = head;
 50 
 51     if(head->data == data)
 52     {
 53         head = head->next;
 54         current->next = NULL;
 55         delete current;
 56         return head;
 57     }
 58 
 59 
 60     while(current)
 61     {
 62         if(current->data == data)
 63             break;
 64         prev = current;
 65         current = current->next;
 66     }
 67 
 68     if(current)
 69     {
 70         prev->next = current->next;
 71         current->next = NULL;
 72         delete current;
 73     }
 74 
 75     return head;
 76 }
 77 
 78 void list_delete(node *head)
 79 {
 80     node *temp;
 81     while(head)
 82     {
 83         temp = head; 
 84         head = head->next;
 85         temp->next = NULL;
 86         delete temp;
 87     }
 88 }
 89 
 90 node* list_insert(node *head, int data)
 91 {
 92     node *node_new = new node;
 93     node_new->data = data;
 94     node_new->next = NULL;
 95 
 96     if(head == NULL)
 97     {
 98         head = node_new;
 99         return head;
100     }
101 
102     if(head->data >= data)
103     {
104         node_new->next = head;
105         head = node_new;
106         return head;
107     }
108 
109     node *prev = head;
110     node *current = head;
111 
112     while(current)
113     {
114         if(current->data < data)
115         {
116             prev = current;
117             current = current->next;
118             continue;
119         }
120         break;
121     }
122 
123     node_new->next = current;
124   prev->next=node_new;      
125     return head;
126 }
127 
128 node *list_rev(node *head)
129 {
130     if(NULL == head)
131         return head;
132 
133     node *prev = head;
134     node *current = head;
135     node *next = head->next;
136 
137 
138     while(next != NULL)
139     {
140         current = next;
141         next = current->next;
142         current->next = prev;
143         prev = current;
144     }
145 
146     head->next = NULL;
147     head = current;
148     return head;
149 }
150 
151 node *create_sort(void)
152 {
153     node * head = NULL;
154     int a = 0;
155     cin >> a;
156     while(a != -1)
157     {
158         head = list_insert(head, a);
159         cin >> a;
160     }
161 
162     return head;
163 }
164 int main(void)
165 {
166     node *head;
167     int num;
168     head = list_create();
169     list_print(head);
170 
171     cout << "input the delete number" << endl;
172     cin >> num;
173 
174     head = node_delete(head, num);
175 
176     list_print(head);
177 
178     list_delete(head);
179 
180     head = create_sort();
181 
182     list_print(head);
183 
184     head = list_rev(head);
185 
186     list_print(head);   
187 
188     list_delete(head);
189 
190     return 0;
191 }                                                                                                       
192