面試題14：反轉鏈表

#include "stdafx.h"   
#include <iostream>   
using namespace std;  
  
struct ListNode  
{  
    int m_nValue;  
    ListNode *m_pNext;  
};  
  
ListNode *ReverseList(ListNode *pListHead)  
{  
    if (pListHead == NULL)  
    {  
        return NULL;  
    }  
  
    ListNode *pReverseHead = NULL;  
    ListNode *pPre = NULL;  
    ListNode *pNode = pListHead;  
    ListNode *pNext = NULL;  
  
    while (pNode != NULL)  
    {  
       pNext = pNode->m_pNext;  
       if (pNext == NULL)  
       {  
           pReverseHead = pNode;             
       }  
       pNode->m_pNext = pPre;  
       pPre = pNode;  
       pNode = pNext;  
    }  
    return pReverseHead;  
}  
  
//創建一個鏈表，輸入從頭到尾結點的值，輸入-1表示結束   
void CreateList(ListNode *& pHead)  
{     
    ListNode *pListNode = NULL;  
    ListNode *pCurLastNode = NULL;  
    bool isHead = true;  
  
    while (1)  
    {  
        if (isHead)  
        {     
            pHead = new ListNode();  
            cin >> pHead->m_nValue;  
            pHead->m_pNext = NULL;  
            isHead = false;  
            pCurLastNode = pHead;  
        }  
        else  
        {  
            pListNode = new ListNode();  
            cin >> pListNode->m_nValue;  
            if (pListNode->m_nValue == -1)  
            {  
                break;  
            }  
            pListNode->m_pNext = NULL;  
            pCurLastNode->m_pNext = pListNode;  
            pCurLastNode = pListNode;     
        }             
    }  
}  
  
//從頭到尾打印鏈表   
void PrintList(ListNode *&pHead)  
{  
    if (pHead != NULL)  
    {  
        ListNode *pCur = pHead;  
        while (pCur != NULL)  
        {  
            cout << pCur->m_nValue << " ";  
            pCur = pCur->m_pNext;  
        }  
        cout << endl;  
    }  
    else  
    {  
        cout << "鏈表為空！" << endl;  
    }  
}  
  
int _tmain(int argc, _TCHAR* argv[])  
{  
    ListNode *pListHead = NULL;  
    CreateList(pListHead);  
    PrintList(pListHead);  
    ListNode *pReverseHead = ReverseList(pListHead);  
    cout << pReverseHead->m_nValue << endl;  
    PrintList(pReverseHead);  
    system("pause");  
    return 0;  
}  
#include "stdafx.h"
#include <iostream>
using namespace std;

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

ListNode *ReverseList(ListNode *pListHead)
{
	if (pListHead == NULL)
	{
		return NULL;
	}

	ListNode *pReverseHead = NULL;
	ListNode *pPre = NULL;
	ListNode *pNode = pListHead;
	ListNode *pNext = NULL;

	while (pNode != NULL)
	{
       pNext = pNode->m_pNext;
	   if (pNext == NULL)
	   {
		   pReverseHead = pNode;		   
	   }
	   pNode->m_pNext = pPre;
	   pPre = pNode;
	   pNode = pNext;
	}
	return pReverseHead;
}

//創建一個鏈表，輸入從頭到尾結點的值，輸入-1表示結束
void CreateList(ListNode *& pHead)
{	
	ListNode *pListNode = NULL;
	ListNode *pCurLastNode = NULL;
	bool isHead = true;

	while (1)
	{
		if (isHead)
		{	
			pHead = new ListNode();
			cin >> pHead->m_nValue;
			pHead->m_pNext = NULL;
			isHead = false;
			pCurLastNode = pHead;
		}
		else
		{
			pListNode = new ListNode();
			cin >> pListNode->m_nValue;
			if (pListNode->m_nValue == -1)
			{
				break;
			}
			pListNode->m_pNext = NULL;
			pCurLastNode->m_pNext = pListNode;
			pCurLastNode = pListNode;	
		}			
	}
}

//從頭到尾打印鏈表
void PrintList(ListNode *&pHead)
{
	if (pHead != NULL)
	{
		ListNode *pCur = pHead;
		while (pCur != NULL)
		{
			cout << pCur->m_nValue << " ";
			pCur = pCur->m_pNext;
		}
		cout << endl;
	}
	else
	{
		cout << "鏈表為空！" << endl;
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	ListNode *pListHead = NULL;
	CreateList(pListHead);
	PrintList(pListHead);
	ListNode *pReverseHead = ReverseList(pListHead);
	cout << pReverseHead->m_nValue << endl;
	PrintList(pReverseHead);
    system("pause");
	return 0;
}