題目：給定一個帶附加頭節(jié)點的單鏈表稀拐，設(shè)first為其頭指針啸澡，節(jié)點的結(jié)構(gòu)為(data,link)，data為數(shù)據(jù)域慰毅，link為指針域隘截，試寫出算法：通過遍歷一趟鏈表，將鏈表中所有節(jié)點逆序連接
分析：這是很經(jīng)典的“單鏈表逆序”問題汹胃。很多公司的面試題庫中都有這道題婶芭，有的公司明確題目要求不能開辟額外的節(jié)點空間（否則可以在遍歷原鏈表的同時使用前插法建立一個逆序鏈表），有的沒有明確說明着饥，但是如果面試者使用了額外的節(jié)點存儲空間犀农，會得到一個比較低的分數(shù)。如何在不使用額外節(jié)點的情況下使一個單鏈表的所有節(jié)點逆序宰掉？我們先用迭代循環(huán)的思想來分析這個問題呵哨。
這種方法需要另外定義一個前驅(qū)指針prev和后繼指針latter赁濒。初始狀態(tài)，p指向當前節(jié)點即第一個節(jié)點A孟害，prev為NULL拒炎，latter指向A的下一個節(jié)點B。鏈表的初始狀態(tài)如下圖所示：
從A節(jié)點開始逆序纹坐，首先將A節(jié)點的link指針指向prev（因為prev的當前值是NULL枝冀，所以A節(jié)點就從鏈表中脫離出來了），然后整體后移耘子，prev指向p果漾，后移p和latter指針。逆向節(jié)點A之后谷誓，鏈表的狀態(tài)如下圖所示：
從圖（1）的初始狀態(tài)到圖（2）狀態(tài)共做了四個操作绒障，這四個操作的偽代碼如下：
p->link = prev;
prev = p;
p = latter;
latter = p->link;
這四行偽代碼就是循環(huán)算法的迭代體了，現(xiàn)在用這個迭代體對圖（2）的狀態(tài)再進行一輪迭代捍歪，就得到了下圖的狀態(tài)：
那么循環(huán)終止條件呢户辱？現(xiàn)在對圖（3）的狀態(tài)再迭代一次得到下圖的狀態(tài)：
此時可以看出，在圖（4）的基礎(chǔ)上再進行一次迭代就可以完成鏈表的逆序糙臼，因此循環(huán)迭代的終止條件就是p指針為NULL庐镐。當然，最后還要注意將附加頭節(jié)點放到首節(jié)點的前面变逃。
源碼：
void List<T>::Inverse()
{
if(first == NULL) return;
LinkNode<T> *p, *prev, *latter;
p = first->link; // 當前結(jié)點
prev = NULL; // 前一結(jié)點
latter = p->link; // 下一結(jié)點
while(p != NULL)
{
p->link = prev; // 當前結(jié)點指針指向前一結(jié)點
prev = p; // 后移
p = latter;
if(p != NULL) // 如果p指針是NULL必逆，已經(jīng)滿足終止條件
latter = p->link;
}
first->link = prev;; // 最后連上附加頭結(jié)點
}
