- 相關推薦
筆試題(單向鏈表)
單向鏈表的反轉是一個經(jīng)常被問到的一個面試題,也是一個非;A的問題。比如一個鏈表是這樣的:
1->2->3->4->5
通過反轉后成為5->4->3->2->1。
最容易想到的方法遍歷一遍鏈表,利用一個輔助指針,存儲遍歷過程中當前指針指向的下一個元素,然
后將當前節(jié)點元素的指針反轉后,利用已經(jīng)存儲的指針往后面繼續(xù)遍歷。源代碼如下:
struct linka {
int data;
linka* next;
};
void reverse(linka*& head) {
if(head ==NULL)
return;
linka *pre, *cur, *ne;
pre=head;
cur=head->next;
while(cur)
{
ne = cur->next;
cur->next = pre;
pre = cur;
cur = ne;
}
head->next = NULL;
head = pre;
}
還有一種利用遞歸的方法。這種方法的基本思想是在反轉當前節(jié)點之前先調用遞歸函數(shù)反轉后續(xù)節(jié)點。
源代碼如下。不過這個方法有一個缺點,就是在反轉后的最后一個結點會形成一個環(huán),所以必須將函數(shù)的
返回的節(jié)點的next域置為NULL。因為要改變head指針,所以我用了引用。算法的源代碼如下:
linka* reverse(linka* p,linka*& head)
{
if(p == NULL || p->next == NULL)
{
head=p;
return p;
}
else
{
linka* tmp = reverse(p->next,head);
tmp->next = p;
return p;
}
}
【筆試題單向鏈表】相關文章:
筆試題(鏈表)09-20
筆試題(鏈表反向)09-19
迅雷2011.10.21筆試題08-10
中興2015筆試題08-02
筆經(jīng):加強型試題07-22
海爾04年筆試題及答案07-31
交通銀行2014筆試題題目分享08-10
阿里巴巴非技術類筆經(jīng)及試題08-13