筆試題（單向連結串列的反轉）

單向連結串列的反轉是一個經常被問到的一個面試題，也是一個非常基礎的問題。比如一個連結串列是這樣的： 1->2->3->4->5 通過反轉後成為5->4->3->2->1。

    最容易想到的.方法遍歷一遍連結串列，利用一個輔助指標，儲存遍歷過程中當前指標指向的下一個元素，然後將當前節點元素的指標反轉後，利用已經儲存的指標往後面繼續遍歷。源程式碼如下：

       1. struct linka {
       2. int data;
       3. linka* next;
       4. };
       5. void reverse(linka*& head) {
       6. if(head ==NULL)
       7.                   return;
       8. linka *pre, *cur, *ne;
       9. pre=head;
      10. cur=head->next;
      11. while(cur)
      12. {
      13.    ne = cur->next;
      14.    cur->next = pre;
      15.    pre = cur;
      16.    cur = ne;
      17. }
      18. head->next = NULL;
      19. head = pre;
      20. }

    還有一種利用遞迴的方法。這種方法的基本思想是在反轉當前節點之前先呼叫遞迴函式反轉後續節點。原始碼如下。不過這個方法有一個缺點，就是在反轉後的最後一個結點會形成一個環，所以必須將函式的返回的節點的next域置為NULL。因為要改變head指標，所以我用了引用。演算法的原始碼如下：

       1. linka* reverse(linka* p,linka*& head)
       2. {
       3. if(p == NULL || p->next == NULL)
       4. {
       5.    head=p;
       6.    return p;
       7. }
       8. else
       9. {
      10.    linka* tmp = reverse(p->next,head);
      11.    tmp->next = p;
      12.    return p;
      13. }
      14. }