鏈表逆轉(zhuǎn)是面試環(huán)境中經(jīng)常遇到的一道題目，也是我們在實(shí)際開發(fā)中可能會遇到的開發(fā)需求。和線性逆轉(zhuǎn)不一樣，單向鏈表的節(jié)點(diǎn)需要一個(gè)一個(gè)進(jìn)行處理。為了顯示兩者之間的區(qū)別，我們分別對線性內(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ù)對原來的數(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）對2）進(jìn)行循環(huán)迭代處理，直到所有的節(jié)點(diǎn)都已經(jīng)接受反轉(zhuǎn)

建議大家可以好好觀察一下兩者之間的區(qū)別。

上一篇：函數(shù)堆棧顯示下一篇：回?cái)?shù)

在线观看不卡亚洲电影_亚洲妓女99综合网_91青青青亚洲娱乐在线观看_日韩无码高清综合久久

鏈表逆轉(zhuǎn)