筆試題單向鏈表

時間：2023-03-24 07:41:21 筆試題目我要投稿

相關推薦

筆試題（單向鏈表）

單向鏈表的反轉是一個經常被問到的一個面試題，也是一個非常基礎的問題。比如一個鏈表是這樣的：

筆試題（單向鏈表）

1->2->3->4->5
通過反轉后成為5->4->3->2->1。
最容易想到的方法遍歷一遍鏈表，利用一個輔助指針，存儲遍歷過程中當前指針指向的下一個元素，然

后將當前節點元素的指針反轉后，利用已經存儲的指針往后面繼續遍歷。源代碼如下：
    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;
    }
還有一種利用遞歸的方法。這種方法的基本思想是在反轉當前節點之前先調用遞歸函數反轉后續節點。

源代碼如下。不過這個方法有一個缺點，就是在反轉后的最后一個結點會形成一個環，所以必須將函數的

返回的節點的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;
    }
    }

【筆試題單向鏈表】相關文章：

中興2015筆試題08-02