经典的单链表逆转


单链表的逆转,有递归与非递归两种实现方式。

非递归的实现中,主要就是不断的移动新链表头,然后让新链表头的next指向上一个新链表头。

递归中,我们控制新的链表头的不断变化,然后让旧链表头的next一直指向下一个新链表的头部。

完整代码如下:

#include <iostream>

using namespace std;

struct NodeList
{
        int value;
        NodeList * next;

        NodeList():
                value(0),
                next(NULL)
        {

        }
};

void createList(NodeList ** head)
{
        int val;

        cout<<"请输入链表数组"<<endl;

        while(cin>>val)
        {
                NodeList * node = new NodeList;
                node->value = val;

                node->next = *head;
                *head = node;
        }
}

void PrintList(NodeList * head)
{
        NodeList * p = head;

        while(p != NULL)
        {
                cout<<p->value<<"\t"<<flush;

                p = p->next;
        }

        cout<<endl;
}

void ReverseList(NodeList ** phead)
{
        NodeList * newhead = *phead;

        NodeList * p  = (*phead)->next;

        newhead->next = NULL;

        while(p != NULL)
        {
                NodeList * q = newhead;

                newhead = p;

                p = newhead->next;

                newhead->next = q;
        }

        *phead = newhead;
}

void ReverseListRecurse(NodeList **head, NodeList *cur)
{
        //use next
        if (NULL == cur->next || NULL == head || NULL == *head)
        {
                return ;
        }

        NodeList *oldhead = *head;

        *head = cur->next;

        NodeList * temp = cur->next->next;
        (*head)->next = oldhead;
        cur->next = temp; 

        ReverseListRecurse(head, cur);
}

void DestroyList(NodeList * head)
{
        NodeList * p = head;

        while(p != NULL)
        {
                NodeList * q = p;

                p = p->next;

                delete q;
        }
}

int main()
{
        NodeList * head = NULL;

        createList(&head);

        PrintList(head);

        cout<<"------------------------"<<endl;
        //ReverseList(&head);
        ReverseListRecurse(&head, head);

        PrintList(head);
}

评论

发表评论