单向链表反转

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

//

// File Name : ReverseLinkedList.cpp

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

// File Date : 2010-07-21

// E-Maile : [e-mail]

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