链表的逆置（又称反转）

转自链表的逆置（又称反转）

#include<stdio.h>

struct ListNode
{
    int m_data;
    struct ListNode * m_pNext;
};

// pPrve pNode pNext
// 正常实现
ListNode* ReverseList(ListNode *pHead)
{
    ListNode* pNode = pHead;
    ListNode* pReversedHead = NULL;
    ListNode* pPrev = NULL;
    while(NULL!=pNode)
    {
        ListNode* pNext = pNode->m_pNext;
        if(NULL == pNext)
            pReversedHead = pNode;

        pNode->m_pNext = pPrev;
        pPrev = pNode;
        pNode = pNext;
        
    }
    return pReversedHead;
}

//递归实现
ListNode* ReverseSingle(ListNode*pNode, ListNode* pPrev)
{
    if(NULL == pNode)
    {
        return pPrev;
    }

    ListNode *pNext = pNode-> m_pNext;
    pNode->m_pNext = pPrev;

    return ReverseSingle(pNext, pNode);

}

ListNode* ReversedListRecursive(ListNode *pHead)
{
    ListNode* pNode = pHead;
    ListNode* pPrev = NULL;
    
    return ReverseSingle(pNode,pPrev);
}

//打印
void printList(ListNode* pHead)
{
    //应加判断pHead不为空

    ListNode* ptemp = pHead;
    while(ptemp != NULL)
    {
        printf("%d ",ptemp->m_data);
        ptemp = ptemp->m_pNext;
    }
    putchar('\n');
}

int main(int argc, char**argv)
{
    int len =10;
    ListNode* pHead = new ListNode;
    pHead->m_data = 10;
    pHead->m_pNext = NULL;
    ListNode* pPrev = pHead;

    for(int i=0;i<len;++i)
    {
        ListNode* p = new ListNode;
        p->m_data = i;
        
        p->m_pNext = pPrev->m_pNext;
        pPrev -> m_pNext = p;
        
    }
    printList(pHead);
    //ListNode* pReversedHead = ReversedListRecursive(pHead);
    ListNode* pReversedHead = ReverseList(pHead);
    printList(pReversedHead);
}