筆試題單向鏈表

筆試題（單向鏈表）

單向鏈表的反轉(zhuǎn)是一個(gè)經(jīng)常被問(wèn)到的一個(gè)面試題，也是一個(gè)非常基礎(chǔ)的問(wè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ù)遍歷。源代碼如下：
    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;
    }
還有一種利用遞歸的方法。這種方法的基本思想是在反轉(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指針，所以我用了引用。算法的源代碼如下：
    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;
    }
    }
 

【筆試題單向鏈表】相關(guān)文章：

筆試題（鏈表）09-20

筆試題（鏈表反向）09-19

迅雷2011.10.21筆試題08-10

中興2015筆試題08-02

筆經(jīng)：加強(qiáng)型試題07-22

海爾04年筆試題及答案07-31

銀行2014筆試題目及經(jīng)驗(yàn)分享03-16

交通銀行2014筆試題題目分享08-10

阿里巴巴非技術(shù)類筆經(jīng)及試題08-13