一文讀懂鏈表反轉（迭代法和遞歸法）

2020 年 7 月 5 日
筆記
數據結構和算法

單向鏈表反轉的方法有很多，其中用的比較多的是迭代法和遞歸法，迭代法通俗易懂，遞歸法相對來說比較難理解一些。

最近讀了一些網上的文章對這兩種算法的解釋後，有些自己的理解分享出來供大家參考。

單向鏈表反轉圖示：

一、迭代法

迭代法的解題思路是：通過循環遍歷的方式，使鏈表的每一個節點和它的下一個節點斷開，然後重置其下一個節點。

代碼實現：

import lombok.AllArgsConstructor;
import lombok.Data;

@Data
@AllArgsConstructor
public class ListNode {

    private int value;

    private ListNode next;


    /**
     * 迭代法
     * @param head
     * @return
     */
    public static ListNode reverseIterate(ListNode head){

        ListNode pre = null,cur = head,next = null;

        while (null != cur){
            next = cur.next;
            cur.next = pre; 
            pre = cur; 
            cur = next;
        }

        return pre;
    }

    public static void main(String[] args) {

        ListNode listNode4 = new ListNode(4, null);
        ListNode listNode3 = new ListNode(3, listNode4);
        ListNode listNode2 = new ListNode(2, listNode3);
        ListNode listNode1 = new ListNode(1, listNode2);

        System.out.println(reverseIterate(listNode1));
        
    }
}

代碼解釋：

對於鏈表中的一個節點(cur)來說，它包含節點的值（value）、其所指向的下一個節點（next）、及指向它的上一個節點（pre）。反轉鏈表就是要把當前節點指向的下一個節點變成指向上一個節點。（鏈表頭沒有上一個節點，鏈表尾下一個節點的指向為空）

next = cur.next; 保留當前節點的下一個節點

cur.next = pre; 重置當前節點的下一個節點為上一個節點

pre = cur; 下次遍歷需要用到的上一個節點

cur = next; 下次遍歷需要用到的當前節點

其執行過程可以用下圖表示：

迭代法的特點是：從前向後節點之間的鏈接依次斷開，重置每個節點下一個節點的指向。

二、遞歸法

遞歸法的解題思路是：利用遞歸的思想和棧先進後出的特性，完成鏈表的反轉。

要理解遞歸法，首先要對遞歸和棧的特性有一定的了解，這裡簡單介紹一下。

遞歸：方法自己調用自己、遞歸需要有結束條件。

棧:先進後出。

要牢記這兩個點，對我們理解遞歸法很重要。

代碼實現：

import lombok.AllArgsConstructor;
import lombok.Data;

@Data
@AllArgsConstructor
public class ListNode {

    private int value;

    private ListNode next;

    /**
     * 遞歸法
     * @param head
     * @return
     */
    public static ListNode reverseRecursion(ListNode head){
        if (null == head || null == head.next){
            return head;
        }

        ListNode newHead = reverseRecursion(head.next);

        head.next.next = head;
        head.next = null;

        return newHead;
    }


    public static void main(String[] args) {

        ListNode listNode4 = new ListNode(4, null);
        ListNode listNode3 = new ListNode(3, listNode4);
        ListNode listNode2 = new ListNode(2, listNode3);
        ListNode listNode1 = new ListNode(1, listNode2);

        System.out.println(reverseRecursion(listNode1));

    }
}

代碼解釋：

ListNode newHead = reverseRecursion(head.next);

1、遞歸法的目的是要返回一個新的頭節點，這個新的頭節點是原來鏈表的尾節點。

2、遞歸是方法自己調用自己，棧的特性是先進後出、後進先出。所以這段代碼的作用是不斷的去壓棧。

head.next.next = head; 把當前節點指向的下一個節點的指向變為自己。（不要慌，這段代碼的解釋，下面有圖有真相）

head.next = null; 當前節點指向的下一個節點變為空。

是不是看了上面的解釋還有點不理解，別急，我第一次看這段代碼的時候也是懵逼的（內心os:這寫了個啥，怎麼就反轉鏈表了）

要理解這段代碼首先，我們得去壓幾個棧，可能你會說我腦子裡壓不了幾個棧容量就不夠了，腦子就亂了，StackOverflowException。。。

講真，我最開始也是想放棄的，背住代碼算了。迭代法他就不香嗎。。。

後來想到人類對圖形的理解能力要長於文字，我們把這個過程畫出來試試看能否理解。

我們還使用上文中使用過的鏈表作為數據源來分析這個過程