天天看點

[LeetCode] Reverse Linked List I II - 連結清單翻轉問題

題目概述:

        reverse a singly linked list.

        翻轉一個單連結清單,如:1->2 輸出 2->1;1->2->3 輸出3->2->1。

題目解析:

        本人真的比較笨啊!首先想到的方法就是通過判斷鍊尾是否存在,再建立一個連結清單,每次移動head的鍊尾元素,并删除head連結清單中的元素,一個字“蠢”,但好歹ac且鞏固了連結清單基礎知識。你可能遇見的錯誤包括:

        1.'listnode' undeclared (first use in this function)

        nhead=(istnode*)malloc(sizeof(listnode));    

                                    =>

        nhead=(struct listnode*)malloc(sizeof(struct listnode));

        2.time limit exceeded

        在連結清單周遊尋找最後一個結點并插入新連結清單尾部中需要注意,建議的方法:

        q=head; while(q) {q=q->next;}

        p=(struct listnode*)malloc(sizeof(struct listnode));

        p->val=head->val; p->next=null; q=p;       

        q=head; while(q) {last=q; q=q->next;} 

        p->val=head->val; p->next=null; last->next=p;

        通過借助last變量更直覺,否則結果總是錯誤。而且此時q為next指向null,如果用到q->next=p就會出現re錯誤,因為q都為null,哪來的q->next。第二個錯誤也可能是我個人的程式設計習慣吧!

        第二種方法更為推薦——直接翻轉,還有一種遞歸方法自行提高。

        如下圖所示,紅色表示初始連結清單存在4個值[1, 2, 3, 4],藍色表示初始指針first指向第一個元素、second指向第二個元素(head->next),third指向第三個元素;首先s->next=f斷開連結清單并翻轉指向第一個元素,同時f=s最後傳回first。如果隻有兩個元素[1, 2]則執行"s->next=f; f=s;"後s=t=null傳回f即可輸出[2, 1]。

[LeetCode] Reverse Linked List I II - 連結清單翻轉問題

我的代碼:

直接翻轉方法

"蠢"方法