 #include <iostream>
  typedef struct __node  {
 int value;
__node* next;
 } NODE, *PNODE;
PNODE reverse(PNODE head) {
  if (!head) {
return head;
 }
PNODE curNode = head;
PNODE nextNode = head->next;
head->next = NULL;
while (nextNode) {
PNODE afterNextNode = nextNode->next;
nextNode->next = curNode;
curNode = nextNode;
nextNode = afterNextNode;
}
return curNode;
}
PNODE reverse_recursionA(PNODE head) {
if (head == NULL || head->next == NULL) {
return head;
}
PNODE temp = reverse_recursionA(head->next);
head->next = temp->next;
temp->next = head;
return head;
}
PNODE reverse_recursionB(PNODE head) {
if (head == NULL || head->next == NULL) {
return head;
}
PNODE temp = reverse_recursionB(head->next);
head->next->next = head;
return temp;
}
PNODE reverse_recursionC(PNODE cur, PNODE pre) {
if (NULL == cur) {
return pre;
}
PNODE temp = cur->next;
cur->next = pre;
return reverse_recursionC(temp, cur);
}
void printList(PNODE head) {
PNODE curNode = head;
while (curNode) {
std::cout << curNode->value << ' ' << std::flush;
curNode = curNode->next;
}
std::cout << std::endl;
}
int main() {
PNODE head = new NODE();
head->value = 0;
head->next = NULL;
PNODE tail = head;
for (int index = 1; index != 100; ++index) {
PNODE newNode = new NODE();
newNode->value = index;
newNode->next = head;
head = newNode;
}
std::cout << "Original: " << std::endl;
printList(head);
head = reverse(head);
std::cout << "After reverse: " << std::endl;
printList(head);
tail = head;
head = reverse_recursionB(head);
tail->next = NULL;
std::cout << "After one reverse_recrusionB: " << std::endl;
printList(head);
reverse_recursionA(head);
PNODE temp = head;
head = tail;
tail = temp;
std::cout << "After reverse_recursionA: " << std::endl;
printList(head);
tail = head;
head = reverse_recursionC(head, NULL);
std::cout << "After reverse_recursionC: " << std::endl;
printList(head);
PNODE curNode = head;
while (curNode) {
PNODE temp = curNode->next;
delete curNode;
curNode = temp;
}
return 0;
}
|