單鏈表及其反轉

單鏈表是一種鏈式存取的資料結構，用一組地址任意的儲存單元存放線性表中的資料元素。鏈表中的資料是以節點來表示的，每個節點由元素和指標構成，元素是儲存資料的儲存單元，指標是連接每個節點的地址資料，本文將介紹什麼是單鏈表以及單鏈表的翻轉，主要內容如下：

什麼是單鏈表
遍歷反轉單鏈表
遞歸反轉單鏈表

什麼是單鏈表#

對於單鏈表的每個節點，都有兩塊儲存區域，一塊儲存對應節點的資料，另一塊儲存該節點的下一個節點的地址，可以稱之為後繼指標 (next)，單鏈表圖示如下：

頭節點：鏈表的第一個節點，用來記錄鏈表的基地址
尾節點：鏈表的最後一個節點，其後繼指標（next）指向空地址

遍歷反轉單鏈表#

記住一點，鏈表反轉實際上就是將鏈表中的指標指向相反方向，假設單鏈表為 A->B->C->D，反轉後則為 D->C->B->A，通過遍歷方式反轉單鏈表就是將每個節點依次反轉。

依次反轉時，A 節點的 next 指標指向 null，然後 B 節點的 next 的指標指向 A 節點，最終遍歷完成單鏈表的反轉，遍歷反轉單鏈表圖示如下：

具體程式碼如下：

/**
 * 鏈表反轉（遍歷）
 *
 * @param head
 * @return
 */
public Node<T> reverse(Node<T> head) {

    /**
     * 思路：對於鏈表A->B->C->D將其反轉就是將頭節點也就是A節點指向null,在將B節點指向A節點，依稀類推
     *      反轉過程中要注意鏈表的斷開，防止丟失斷開的鏈表
     *
     * 鏈表反轉實際上就是將鏈表中的指標指向相反方向
     */

    Node<T> tempNode = null;
    while (head != null) {
        // 記錄因為反轉斷開的鏈表
        Node<T> nextNode = head.next;
        // 鏈表反轉
        head.next = tempNode;
        // 移動tempNode指標
        tempNode = head;
        // 移動head指標
        head = nextNode;
    }
    return tempNode;
}

遞歸反轉單鏈表#

第二種反轉單鏈表的方式就是遞歸，核心思想就是大問題轉小問題，通俗來講就是多個節點的單鏈表都是都可以進一步劃分為更小的單鏈表，如一個節點的單鏈表就是它本身，兩節點點的單鏈表 A->B->null，反轉時將相鄰節點指標反向即可，即將節點 B 的 next 指標指向 A，此時 A 的 next 指標還是指向 B，所以需要將 A 的 next 指標指向 null，程式碼表示如下：

// 鏈表A->B->null反轉
B.next = A;
A.next = null;

使用遞歸方式反轉單鏈表圖示如下：

具體程式碼如下：

/**
 * 鏈表反轉（遞歸）
 *
 * @param head
 * @return
 */
public Node<T> reverse(Node<T> head) {

    /**
     * 思路：使用遞歸思想解決
     *
     * 鏈表反轉始終要記得兩個相鄰節點的指標反向
     */

    if (head == null || head.next == null) {
        return head;
    }
    
    // newNode即最終反轉後的頭節點
    Node<T> newNode = reverse1(head.next);
    head.next.next = head;
    head.next = null;
    return newNode;
}

如上介紹了單鏈表及其反轉的兩種方式，如有錯誤歡迎指正。