编辑代码

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <stack>
using namespace std;

//C++ 版本
struct Node{
    int data;
    Node *next;
};

//Node *head;   //声明全局变量 head

// 头部插入值
Node* insert(Node* head,int x){
    Node *temp1 = new Node();
    temp1 -> data = x;
    temp1 -> next = NULL;
    if(head == NULL){
        head = temp1;
        return head;
    }
    //Node *temp2 = head;
    //temp1 -> next = temp2 -> next;
    //temp2 -> next = temp1;
    temp1 -> next = head;
    head = temp1;
    return head;
}

//遍历打印链表
void print(Node* head){
    Node *temp = head;
    while(temp != NULL){
        printf("%d ",temp -> data);
        temp = temp -> next;
    }
    printf("\n");
}

//栈反转
Node* Reverse(Node* head){
    if(head == NULL) return head;
    Node* currentNode = head;
    stack<struct Node*> S;
    while(currentNode != NULL){
        S.push(currentNode);
        currentNode = currentNode -> next;
    }
    currentNode = S.top();
    head = currentNode;
    S.pop();
    while(!S.empty()){
        currentNode -> next = S.top();
        S.pop();
        currentNode = currentNode -> next;
    }
    currentNode -> next = NULL;
    return head;
}

//迭代反转
Node* Reverse1(Node* head){
    Node* current = head;
    Node* pre = NULL;
    Node* next = NULL;
    while(current != NULL){
        next = current -> next;
        current -> next = pre;
        pre = current;
        current = next;
    }
    head = pre;
    return head;
}

// void Delete(Node* head){
//     while(head != NULL){
//     Node* temp = head;
//     while(temp != NULL){
//         temp = temp -> next;
//     }
//     delete(temp);
//     } 
// }

//递归反转
Node* Reverse2(Node* currentNode){
	Node* head = NULL; 
	if(currentNode -> next == NULL){
		head = currentNode;
		return head;
	}
	head = Reverse2(currentNode -> next);
	Node* nextNode = currentNode -> next;
	nextNode -> next = currentNode;
	currentNode -> next = NULL;
	return head;
}

int main() {
    Node* head = NULL;
    head = insert(head,2);
    head = insert(head,5);
    head = insert(head,10);
    head = insert(head,15);
    head = insert(head,19);
    print(head);
    head = Reverse1(head);
    print(head);

    head = Reverse2(head);
    print(head);

    head = Reverse(head);
    print(head);
}