題目：
定義一個函數，輸入一個連結清單的頭結點，反轉該連結清單并輸出反轉後連結清單的頭結點。連結清單結點定義如下：
struct ListNode{
int m_nKey,
ListNode * m_pNext;
}
思路：
為了正确地反轉一個連結清單，需要調整連結清單中指針的方向。為了将複雜的過程說清楚，這裡借助于下面的這張圖檔。
上面的圖中所示的連結清單中，h、i和j是3個相鄰的結點。假設經過若幹操作，我們已經把h結點之前的指針調整完畢，這個結點的m_pNext都指向前面的一個結點。接下來我們把i的m_pNext指向h，此時結構如上圖所示。
從上圖注意到，由于結點i的m_pNext都指向了它的前一個結點，導緻我們無法在連結清單中周遊到結點j。為了避免連結清單在i處斷裂，我們需要在調整結點i的m_pNext之前，把結點j儲存下來。
即在調整結點i的m_pNext指針時，除了需要知道結點i本身之外，還需要i的前一個結點h，因為我們需要把結點i的m_pNext指向結點h。同時，還需要實作儲存i的一個結點j，以防止連結清單斷開。故我們需要定義3個指針，分别指向目前周遊到的結點、它的前一個結點及後一個結點。故反轉結束後，新連結清單的頭的結點就是原來連結清單的尾部結點。尾部結點為m_pNext為null的結點。
代碼實作：
public class ListNode {
public int data;
public ListNode next;
} public ListNode reverseList(ListNode pHead){
ListNode pReversedHead = null; //反轉過後的單連結清單存儲頭結點
ListNode pNode = pHead; //定義pNode指向pHead;
ListNode pPrev = null; //定義存儲前一個結點
while(pNode != null){
ListNode pNext = pNode.next; //定義pNext指向pNode的下一個結點
if(pNext==null){ //如果pNode的下一個結點為空，則pNode即為結果
pReversedHead = pNode;
}
pNode.next = pPrev; //修改pNode的指針域指向pPrev
pPrev = pNode; //将pNode結點複制給pPrev
pNode = pNext; //将pNode的下一個結點複制給pNode
}
return pReversedHead;
} 小結：
這道題考查我們是否真正的了解了單連結清單的結構，以及在反轉單連結清單時對指針的修改。
擴充：
我們知道這個題其實是可以用遞歸實作使單連結清單變成反轉連結清單。
public ListNode reverseList3(ListNode pHead){
if(pHead==null || pHead.next == null){ //如果沒有結點或者隻有一個結點直接傳回pHead
return pHead;
}
ListNode pNext = pHead.next; //儲存目前結點的下一結點
pHead.next = null; //打斷目前結點的指針域
ListNode reverseHead = reverseList3(pNext); //遞歸結束時reverseHead一定是新連結清單的頭結點
pNext.next = pHead; //修改指針域
return reverseHead;
}