当前位置: 首页 >> 程序设计 >> 数据结构和算法 >> 链表反转的两种实现方法

链表反转的两种实现方法

作者：kubobo 来源：kubobo.cublog.cn 发表时间：2006-11-06 浏览次数：字号：大 中 小

对于链表的讨论似乎永远都不会过时。虽然现在有了容器，但是一味的使用它们，也使自己失去了锻炼的机会。前不久被导师问及链表反转的问题，结果编码、调试，费了好大功夫才算完成了。而且，代码还没得到优化，完善。想不到许久没碰指针，对指针的操作竟生疏了不少。看来对技术的学习，真的不能放松啊～！

把代码简单整理下，大家参考：

#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;
}

界图如下：