鏈表逆轉(zhuǎn)是面試環(huán)境中經(jīng)常遇到的一道題目，也是我們?cè)趯?shí)際開發(fā)中可能會(huì)遇到的開發(fā)需求。和線性逆轉(zhuǎn)不一樣，單向鏈表的節(jié)點(diǎn)需要一個(gè)一個(gè)進(jìn)行處理。為了顯示兩者之間的區(qū)別，我們分別對(duì)線性內(nèi)存和鏈表進(jìn)行逆轉(zhuǎn)：
（1）普通連續(xù)內(nèi)存數(shù)據(jù)的反轉(zhuǎn)分析
- 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;
- }
我們看到連續(xù)內(nèi)存反轉(zhuǎn)函數(shù)主要做了下面幾個(gè)工作：
1）分配和原來數(shù)據(jù)一樣大的內(nèi)存
2）從原來數(shù)據(jù)末尾開始拷貝
3）利用pData獲取的數(shù)據(jù)對(duì)原來的數(shù)據(jù)進(jìn)行拷貝覆蓋，釋放內(nèi)存
（2）鏈表數(shù)據(jù)的反轉(zhuǎn)
- 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;
- }
和連續(xù)內(nèi)存不同，鏈表節(jié)點(diǎn)的反轉(zhuǎn)需要進(jìn)行下面一些操作：
1） 判斷指針是否為空，判斷指針的指針是否為空
2） 將指針分成兩個(gè)部分，一個(gè)是已經(jīng)反轉(zhuǎn)成功的鏈表，即pNode；另外一個(gè)是待反轉(zhuǎn)的鏈表，即pPrevNode
3） 對(duì)2）進(jìn)行循環(huán)迭代處理，直到所有的節(jié)點(diǎn)都已經(jīng)接受反轉(zhuǎn)
