单链表逆序

转自：http://blog.csdn.net/raul23551984/article/details/4330181

view plain

//已知链表的头结点head,写一个函数把这个链表逆序 ( Intel)
#include

using namespace std;

struct Node
{
    int data ;
    Node *next ;
};
typedef struct Node Node ;

Node* ReverseList(Node* head)
{
    if (!head || !head->next)
    {
        return head;
    }
    Node* p1 = head;
    Node* p2 = p1->next;
    head->next = NULL;
    while (p2)
    {

        p1 = p2;
        p2 = p2->next;
        p1->next = head;
        head = p1;
    }
    return head;
}

Node* RecReverseList(Node* head) //递归方法
{
    if (!head || !head->next)
    {
        return head;
    }
    Node *newhead = RecReverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return newhead;
}

void main()
{
    Node a, b, c;
    a.data = 1, a.next = &b;
    b.data = 2, b.next = &c;
    c.data = 3, c.next = NULL;
    Node* tmp = &a;
    while(tmp)
    {
        cout<data<<" ";
        tmp = tmp->next;
    }
    cout<
    tmp = RecReverseList(&a);
    while(tmp)
    {
        cout<data<<" ";
        tmp = tmp->next;
    }
    cout<
}