【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
鏈表逆轉是面試環境中經常遇到的一道題目，也是我們在實際開發中可能會遇到的開發需求。和線性逆轉不一樣，單向鏈表的節點需要一個一個進行處理。為了顯示兩者之間的區別，我們分別對線性內存和鏈表進行逆轉：
（1）普通連續內存數據的反轉分析
STATUS normal_revert(int array[], int length)
{
int* pData ;
int index = length - 1;
if(NULL == array || 0 == length)
return FALSE;
pData = (int*)malloc(sizeof(int) * length);
assert(NULL != pData);
memset(pData, 0, sizeof(int) * length);
while(index >= 0)
pData[length - 1 - index] = array[index], index --;
memmove(array, pData, length * sizeof(int));
free(pData);
return TRUE;
}
STATUS normal_revert(int array[], int length)
{
int* pData ;
int index = length - 1;
if(NULL == array || 0 == length)
return FALSE;
pData = (int*)malloc(sizeof(int) * length);
assert(NULL != pData);
memset(pData, 0, sizeof(int) * length);
while(index >= 0)
pData[length - 1 - index] = array[index], index --;
memmove(array, pData, length * sizeof(int));
free(pData);
return TRUE;
}
我們看到連續內存反轉函數主要做了下面幾個工作：
1）分配和原來數據一樣大的內存
2）從原來數據末尾開始拷貝
3）利用pData獲取的數據對原來的數據進行拷貝覆蓋，釋放內存
（2）鏈表數據的反轉
STATUS link_revert(NODE** pNode)
{
NODE* pPrevNode;
NODE* pNextNode;
if(NULL == pNode || NULL == *pNode)
return FALSE;
pNextNode = (*pNode)->next;
(*pNode) ->next = NULL;
while(pNextNode){
pPrevNode = pNextNode;
pNextNode = pNextNode->next;
pPrevNode->next = *pNode;
*pNode = pPrevNode;
}
return TRUE;
}
STATUS link_revert(NODE** pNode)
{
NODE* pPrevNode;
NODE* pNextNode;
if(NULL == pNode || NULL == *pNode)
return FALSE;
pNextNode = (*pNode)->next;
(*pNode) ->next = NULL;
while(pNextNode){
pPrevNode = pNextNode;
pNextNode = pNextNode->next;
pPrevNode->next = *pNode;
*pNode = pPrevNode;
}
return TRUE;
}和連續內存不同，鏈表節點的反轉需要進行下面一些操作：
1） 判斷指針是否為空，判斷指針的指針是否為空
2） 將指針分成兩個部分，一個是已經反轉成功的鏈表，即pNode；另外一個是待反轉的鏈表，即pPrevNode
3） 對2）進行循環迭代處理，直到所有的節點都已經接受反轉
建議大家可以好好觀察一下兩者之間的區別
