反轉鏈表

20171112 發布于2019-08-14 15:16 / 1477人閱讀

摘要：扯淡之前聽說過面試反轉鏈表的梗，也嘗試著自己實現了一次，算是比較簡單的問題。當然，前提是我們只持有頭節點的引用，且稱為，那么鏈表反轉后的頭節點，就是。

扯淡

之前聽說過google面試反轉鏈表的梗，也嘗試著自己實現了一次，算是比較簡單的問題。但在紙上手寫代碼的時候，思維就很亂，可能是隔的時間長忘記了，或者之前就跟本沒有理清思路，所以被虐的很慘。
這篇文章的目的就是梳理一下思路，加深印象。如果有更好的算法，留言求虐啊～

描述

這是一個普通的鏈表，由ABCD4個節點組成，每個節點都包含數據區-data和指向下一個節點的引用-next

反轉鏈表，顧名思義就是將鏈表每個節點的next引用反過來，如ABCD，變為DCBA。當然，前提是我們只持有頭節點的引用，且稱為Node a，那么鏈表反轉后的頭節點，就是Node d。

分析

要將此鏈表反轉，我們核心的需求是：修改每一個節點的next引用，將next指向前一個節點，將原來的頭節點A中的next，指向null。

既然每一個節點都需要操作，那就考慮循環吧，設一個索引（或者稱為游標）node（可以利用節點A的引用），從節點A跑到節點D，當它再往后移動指向null時，循環結束。那么循環邊界條件則為

while(node != null){
//do something
}

然后我們再看看每個節點做一次反轉（即每次循環），都需要做什么事情

在修改當前節點的next引用之前，要先保存其值，為了避免丟失下一個節點（即Node next）的引用。

進行反轉，修改當前節點的next，使之指向上一個節點（即Node last）

要保存當前節點的引用，為了提供給下一次循環時，對下個節點進行反轉

為了保證while循環可以從頭節點A遍歷到尾節點D，那么游標node在循環體最后要向后移動一個節點，即指向下一個節點。

代碼

Node reversalLinkedList(Node node){
    Node last = null;
    Node next = null;
    while(node != null){
        next = node.getNext();//1 拿到下個節點的引用，為了提供給第4步使node向鏈表后方移動
        node.setNext(last);//2 將當前節點指向上一個節點
        last = node;//3 將last指向當前節點，提供給下次循環的第2步
        node = next;//4 將當前節點的引用（即游標）指向下一個節點        
    }
    /*
    * 循環完成后，node和next都指向了原節點D的next指向的位置，即null
    * 而last指向了上述null前面的位置，即節點D
    * 將last返回，則得到鏈表ABCD反轉后鏈表DCBA的頭節點D
    */
    return last;
}

邏輯其實很簡單，需要注意的就是每次循環時需要暫存的引用 -- next,last

圖解

每次循環其實就是修改當前節點next的引用+三個引用(last,node,next)的后移，如下圖

第一次循環前

第一次循環的過程

第一次循環結束后

最后全部反轉后

總結

保存當前節點，上一個節點，下一個節點的引用

每次循環最后，當前節點向后移動

云服務器 GPU云服務器 python反轉鏈表反轉函數反轉數組反轉

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65550.html

劍指offer系列——劍指 Offer 24. 反轉鏈表（C語言）

摘要：假設反轉對象節點為，反轉指向的結點為，反轉后指向的結點為首結點。當然也可以根據棧先進后出的特點，使用棧反轉鏈表。 ??前面的話?? 大家好！博主開辟了一個新的專欄—...

weakish 2021-09-03 10:29 評論0 收藏0
LeetCode 之 JavaScript 解答第206題 —— 反轉鏈表（Reverse Link

摘要：算法思路兩種方法一般反轉遞歸法一般解決定義三個指針，分別為，存儲當前結點，指向反轉好的結點的頭結點，存儲下一結點信息。遞歸法重點分析先確定終止條件當下一結點為時，返回當前節點判斷當前的鏈表是否為遞歸找到尾結點，將其存儲為頭結點。 Time：2019/4/23Title: Reverse Linked ListDifficulty: EasyAuthor: 小鹿題目：Reverse...

zhangfaliang 2019-08-23 17:12 評論0 收藏0
【面試算法】鏈表反轉

摘要：今天來將一下面試中經常問到的一個問題鏈表反轉。題目給一個單向鏈表，請編寫一個函數，把鏈表反轉，并把反轉的鏈表返回。假設給的節點為雙向鏈表反轉函數如下今天來將一下面試中經常問到的一個問題：鏈表反轉。【題目1】給一個單向鏈表，請編寫一個函數，把鏈表反轉，并把反轉的鏈表返回。假設給的節點為 class ListNode{ int val; ListNode next; ...

adam1q84 2019-08-14 15:19 評論0 收藏0
LeetCode：206. 反轉鏈表

摘要：示例輸入輸出進階你可以迭代或遞歸地反轉鏈表。可以設置一個指針，指向，保證后續的操作然后將，往前挪動，當然還有，直到為空，這時指向反轉后鏈表的頭結點。接下來考慮遞歸結束的條件非常顯然，子鏈表只有一個節點是遞歸結束，直接返回該節點。本文來自 SoulOH 的CSDN 博客，原文地址請點擊：https://blog.csdn.net/SoulOH/... 題目:反轉一個單鏈表。示例: ...

wenshi11019 2019-08-23 12:08 評論0 收藏0