链表反转的两种实现方法

#include <iostream>

using namespace std;

//元结点
struct Node
{
    int data;
    Node *next;
};

//链表反转（循环方法）
Node *Reverse(Node *head)
{
    Node *prev = NULL;
    Node *cur = NULL;
    Node *next = head;

    for (; next != NULL; )
    {
        cur = next;
        next = cur->next;
        cur->next = prev;
        prev = cur;
    }

    return prev;
}

//链表反转（递归方法）
Node *Reverse2(Node *head)
{
    if (!head)
    {
        return NULL;
    }

    Node *temp = Reverse2(head->next);

    if (!temp)
    {
        return head;
    }

    head->next->next = head;
    head->next = NULL;

    return temp;
}

//创建链表
Node *Construct(int *const array, int len)
{
    Node *pre = NULL, *head = NULL;

    for (int i = len; i > 0; i--)
    {
        if (!pre)
        {
            head = new Node;
            head->data = array[len - i];
            head->next = NULL;
            pre = head;
        }
        else
        {
            pre->next = new Node;
            pre = pre->next;
            pre->data = array[len - i];
            pre->next = NULL;
        }
    }

    return head;
}

//销毁链表
void Destruct(Node *head)
{
    Node *cur = head, *temp = NULL;

    while (cur)
    {
        temp = cur;
        cur = cur->next;
        delete temp;
    }
}

//打印链表
void Print(Node *head)
{
    Node *cur = head;

    for (; cur != NULL; cur = cur->next)
    {
        cout << "data: " << cur->data << endl;
    }
}

int main(int argc, char* argv[])
{
    Node *head = NULL;
    int array[] = {1, 3, 5, 7, 9, 10, 8, 6, 4, 2};

    cout << endl << "Construct!" << endl << endl;
    head = Construct(array, 10);
    Print(head);
    cout << endl << "Reverse!" << endl << endl;
    head = Reverse(head);
    Print(head);
    cout << endl << "Reverse2!" << endl << endl;
    head = Reverse2(head);
    Print(head);
    cout << endl << "Destruct!" << endl << endl;
    Destruct(head);
    head = NULL;
    Print(head);

    return 0;
}