- 相關(guān)推薦
筆試題(單向鏈表的反轉(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.oriental01.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)橐淖僪ead指針,所以我用了引用。算法的源代碼如下: 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
寫(xiě)出程序把一個(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