鏈表的逆置常作為應屆生面試題,主要考察求職者對鏈表的理解,還有思維能力。逆置的思路主要是保存幾個臨時的指針變量,其實好多面試題都可以通過保存臨時變量的方式來解決。
C++代碼如下:
#include "stdafx.h" struct ListNode { int m_nData; ListNode* m_pNext; }; ListNode* ReverseList(ListNode *pHead) { ListNode* pReversedHead = NULL; ListNode* pNode = pHead; 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; } int _tmain(int argc, _TCHAR* argv[]) { int len = 10; ListNode *pHead = new ListNode; pHead->m_nData = 10; pHead->m_pNext = NULL; ListNode *pPrev = pHead; for (int i=0; i<len; i++) { ListNode *p = new ListNode; p->m_nData = i; p->m_pNext = NULL; if (NULL != pPrev) { pPrev->m_pNext = p; } pPrev = p; } ListNode *pReversedHead = ReverseList(pHead); return 0; }