單鏈表 和 雙鏈表的翻轉(zhuǎn)

鏈表的屬于非?；A(chǔ)的數(shù)據(jù)結(jié)構(gòu)，但是想要完成好它需要大量的練習，才能夠在面試中不慌不亂的寫好。

先分享今天聽到的一個理論，來自《考試腦科學這本書》中：書中闡述了關(guān)于如何將普通的記憶轉(zhuǎn)換成長期記憶。長期記憶的管理員是一個叫海馬體的東西，由這個管理員來判斷這個記憶是否值得放進長期記憶存儲區(qū)域。那這個管理員判斷的標準是什么呢？

標準是這個東西跟生活的危險有沒有關(guān)系，你只要被開水壺燙過一次你就會永遠記住不能摸開水壺。那么跟生活危險沒關(guān)系的知識想要進入長期存儲區(qū)怎么辦？那只能去欺騙海馬體了。。想要欺騙它你需要的重復練習，一直在管理員面前轉(zhuǎn)悠，這時候管理員就會在想，這人是不是真的有事 啊？要不要放它進去？進去了長期記憶就形成了。

還有一個方法，將自己置于對自己稍微不利的境地（當然這里指的是不太嚴重的?。。热缯f肚子餓的時候，這時候海馬體就會把你和危險聯(lián)系起來，這時候就是背東西的最好時機了！沖沖沖

接下來開始看單鏈表翻轉(zhuǎn)的練習

首先我們來看看單鏈表的翻轉(zhuǎn)的代碼，然后會畫圖來解釋這個代碼是怎么回事：

最簡單的鏈表翻轉(zhuǎn)當然是用java中的容器去做，將鏈表左右節(jié)點都放入容器中，然后反向遍歷容器中的元素連接就行了，這樣額外空間復雜度是的，這里就不做代碼闡述了。這里主要講的是如何用額外空間復雜度去翻轉(zhuǎn)鏈表。

public class ReverseList {

    public static class Node { // 基本的鏈表節(jié)點聲明
        public int value;
        public Node next;

        public Node(int data) {
            value = data;
        }
    }

    public static Node reverseLinkedList(Node head){
        Node pre = null;  // 記錄 頭節(jié)點的 前一個地方 的指針
        Node next = null; // 記錄 頭節(jié)點的 下一個要去的地方 的指針

        while(head != null){
            next = head.next; // 首先 先要記錄好頭節(jié)點的下一個地方，才不至于翻轉(zhuǎn)之后不知道下一個地方要去哪
            head.next = pre; // 然后將 頭節(jié)點的下一個地方 指向頭節(jié)點的前一個地方
            pre = head; // 將 記錄頭節(jié)點的前一個地方的指針 移動到頭指針的地方
            head = next; // 然后頭指針也移動到下一個地方，循環(huán)往復直到頭指針指向空處
        }
        return pre; // 記住我們要返回的是頭指針前一個節(jié)點哦！因為頭指針最終會指向空
    }
}

①：循環(huán)之前我們先準備好兩個指針，一個是pre一個是next，pre指向的是head前面的一個節(jié)點??！
②：然后開始進入循環(huán)，循環(huán)的條件是head指向空就終止??！這時候我們先記錄head的下一個環(huán)境，當head的指針往前指的時候我們就還能找到它下一個節(jié)點在哪。
③：這時候?qū)ead.next指向他的前一個環(huán)境，也就是pre。因為pre是空所以next就置為空了。
④：接下來我們需要做的就是將pre和head向前移動，所以第四歩就是將pre移動到head的位置。
⑤：將head移動到next的地方。

當head指向C的時候循環(huán)是不會判斷為空的，所以這時候它還會進一次循環(huán)，然后指向空，所以最后一個循環(huán)的時候pre會指向C，所以我們最終會返回pre當成頭節(jié)點。

注：圖中有些地方畫的不準確，為了方便理解。

圖解代碼流程

接下來是雙向鏈表，代碼和單鏈表一樣，只多了一行，用來維護last的代碼：

public class ReverseDoubleLinkedList {

    public static class DoubleNode {
        public int value;
        public DoubleNode last;
        public DoubleNode next;

        public DoubleNode(int data) {
            value = data;
        }
    }

    public static DoubleNode reverseDoubleList(DoubleNode head){
        DoubleNode pre = null;
        DoubleNode next = null;

        while(head != null){
            next = head.next;
            head.next = pre;
            head.last = next;
            pre = head;
            head = next;
        }
        return pre;
    }
}

Reference： https://italk.mashibing.com/course/detail/cour_00004003