單鏈表及其反轉

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

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

什麼是單鏈表#

對於單鏈表的每個結點，都有兩塊儲存區域，一塊儲存對應節點的資料，另一塊儲存該節點的下一個結點的地址，可以稱之為後繼指針 (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;
}

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