筆試題（單向鏈表的反轉(zhuǎn)）

單向鏈表的反轉(zhuǎn)是一個(gè)經(jīng)常被問(wèn)到的一個(gè)面試題，也是一個(gè)非�；�礎(chǔ)的問(wèn)題，

筆試題（單向鏈表的反轉(zhuǎn)）

。比如一個(gè)鏈表是這樣的： 1->2->3->4->5 通過(guò)反轉(zhuǎn)后成為5->4->3->2->1。

    最容易想到的方法遍歷一遍鏈表，利用一個(gè)輔助指針，存儲(chǔ)遍歷過(guò)程中當(dāng)前指針指向的下一個(gè)元素，然后將當(dāng)前節(jié)點(diǎn)元素的指針?lè)崔D(zhuǎn)后，利用已經(jīng)存儲(chǔ)的指針往后面繼續(xù)遍歷。源代碼如下：

       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. }

    還有一種利用遞歸的方法，

資料共享平臺(tái)

《筆試題（單向鏈表的反轉(zhuǎn)）》(http://www.lotusphilosophies.com)。這種方法的基本思想是在反轉(zhuǎn)當(dāng)前節(jié)點(diǎn)之前先調(diào)用遞歸函數(shù)反轉(zhuǎn)后續(xù)節(jié)點(diǎn)。源代碼如下。不過(guò)這個(gè)方法有一個(gè)缺點(diǎn)，就是在反轉(zhuǎn)后的最后一個(gè)結(jié)點(diǎn)會(huì)形成一個(gè)環(huán)，所以必須將函數(shù)的返回的節(jié)點(diǎn)的next域置為NULL。因?yàn)橐�改變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. }
 

【筆試題單向鏈表的反轉(zhuǎn)】相關(guān)文章：

鏈表面試題-一個(gè)鏈表的結(jié)點(diǎn)結(jié)構(gòu)08-09

C++筆試題：關(guān)于鏈表和指針09-16

360筆試題目06-27

筆美國(guó)國(guó)家儀器試題目09-23

搜狐產(chǎn)品筆歸分享筆試題目07-05

筆試實(shí)例：判斷單鏈表中是否存在環(huán)08-03

寫出程序把一個(gè)鏈表中的接點(diǎn)順序倒排10-13

最新江河創(chuàng)建調(diào)研報(bào)告：業(yè)績(jī)反轉(zhuǎn)確認(rèn)，多元轉(zhuǎn)型加速09-07

新浪筆經(jīng)04-27

新聞總署筆經(jīng)10-13