单向链表反转

时间：2010-07-22 来源：laiboy

///////////////////////////////////////////////////////////////////////////////

//

// File Name : ReverseLinkedList.cpp

// File Author : DannyLai(L.F.)

// File Date : 2010-07-21

// E-Maile : [email protected]

// Blog : http://laiboy.cublog.cn

// : http://blog.csdn.net/laiboy

// Description : 实现反转单向链表方法

//

///////////////////////////////////////////////////////////////////////////////

#include <iostream>
using namespace std;

template< typename T >
class LinkNode
{
public:
    LinkNode* ptrLinkNode;
    T data;
};

LinkNode< int >* p = NULL;

void InitializeLinkNodes();
void ReleaseLinkNodes();

void PrintLinkNodes();

void ReverseLinkNodesNormal();

int main()
{
    cout << "Reverse Linked List" << endl;

    InitializeLinkNodes();

    PrintLinkNodes();

    ReverseLinkNodesNormal();
    PrintLinkNodes();

    ReleaseLinkNodes();

    return 0;
}

void InitializeLinkNodes()
{
    LinkNode< int >* p1 = new LinkNode< int >;
    LinkNode< int >* p2 = new LinkNode< int >;
    LinkNode< int >* p3 = new LinkNode< int >;
    LinkNode< int >* p4 = new LinkNode< int >;
    LinkNode< int >* p5 = new LinkNode< int >;

    p1->ptrLinkNode = p2;
    p1->data = 1;

    p2->ptrLinkNode = p3;
    p2->data = 2;

    p3->ptrLinkNode = p4;
    p3->data = 3;

    p4->ptrLinkNode = p5;
    p4->data = 4;

    p5->ptrLinkNode = NULL;
    p5->data = 5;

    p = p1;
}

void ReleaseLinkNodes()
{
    LinkNode< int >* pTemp = NULL;

    while ( p != NULL ) {
        pTemp = p;
        p = p->ptrLinkNode;

        cout << "[RELEASE] " << pTemp->data << endl;

        delete pTemp;
        pTemp = NULL;
    }

    p = NULL;
}

void PrintLinkNodes()
{
    LinkNode< int >* pTemp = p;

    cout << "[NODES] ";
    while ( pTemp != NULL ) {
        cout << pTemp->data << " ";

        pTemp = pTemp->ptrLinkNode;
    }
    cout << endl;
}

// 利用临时变量反向链表

void ReverseLinkNodesNormal()
{
    cout << "ReverseLinkNodesNormal" << endl;

    // 处理边界条件: 1.节点空 2.节点只有一个

    if ( p == NULL )
        return;
    if ( p->ptrLinkNode == NULL )
        return;

    LinkNode< int >* pCurrent = p;
    LinkNode< int >* pLast = p;
    LinkNode< int >* pPrevent = NULL;
    LinkNode< int >* pNext = pCurrent->ptrLinkNode;

    // 最后节点

    while ( pLast->ptrLinkNode != NULL ) {
        pLast = pLast->ptrLinkNode;
    }

    while ( pCurrent != pLast ) {
        pCurrent->ptrLinkNode = pPrevent;

        pPrevent = pCurrent;
        pCurrent = pNext;
        pNext = pCurrent->ptrLinkNode;
    }

    pLast->ptrLinkNode = pPrevent;
    p = pLast;
}