一步一步寫算法（之連結清單逆轉）

【 聲明：版權所有，歡迎轉載，請勿用于商業用途。  聯系信箱：feixiaoxing @163.com】

    連結清單逆轉是面試環境中經常遇到的一道題目，也是我們在實際開發中可能會遇到的開發需求。和線性逆轉不一樣，單向連結清單的節點需要一個一個進行處理。為了顯示兩者之間的差別，我們分别對線性記憶體和連結清單進行逆轉：

    （1）普通連續記憶體資料的反轉分析

我們看到連續記憶體反轉函數主要做了下面幾個工作：

    1）配置設定和原來資料一樣大的記憶體

    2）從原來資料末尾開始拷貝 

    3）利用pData擷取的資料對原來的資料進行拷貝覆寫，釋放記憶體

    （2）連結清單資料的反轉

和連續記憶體不同，連結清單節點的反轉需要進行下面一些操作：

    1） 判斷指針是否為空，判斷指針的指針是否為空

    2） 将指針分成兩個部分，一個是已經反轉成功的連結清單，即pNode；另外一個是待反轉的連結清單，即pPrevNode

    3） 對2）進行循環疊代處理，直到所有的節點都已經接受反轉

    建議大家可以好好觀察一下兩者之間的差別。