Reverse a singly linked list.

這個篇章一開始也拋了一個問題出來，【反轉一個單向的鏈結陣列】，這問題感覺起來並不難解，只要從頭開始往後遍歷，把後面的節點都設定在開頭就好了，用文字有點難解釋，Explore Card 有提供圖片展示過程，以下直接進入反轉鏈結陣列的題目講解。

206. Reverse Linked List

題目

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Constraints:

• The number of nodes in the list is the range [0, 5000].
• 5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

解法(Java)

這題我也嘗試了兩種解法，第一種解法跟Explore Card 上面的概念一樣，遍歷鏈結陣列的節點，不斷把後面的節點設定為鏈結陣列的開頭。

Runtime: 0 ms (97.58%)
Memory Usage: 40.8 MB

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode result = null;
        ListNode temp = null;
        do {
            temp = head.next;
            head.next = result;
            result = head;
            head = temp;
        } while (head != null);

        return result;
    }
}

第二個解法一樣是遍歷整個鏈結陣列，只是最終結果是不斷建立新的節點進行串聯，但在記憶體使用量上差不多，時間上卻慢了10%。

Runtime: 0 ms (86.57%)
Memory Usage: 40.9 MB

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) return null;

        ListNode result = new ListNode(head.val);
        while (head.next != null) {
            head = head.next;
            result = new ListNode(head.val, result);
        }

        return result;
    }
}

解法概念

這個章節還有提供其他題目可以練習鏈結陣列，雖然Explore Card 是解完之後才會提供，但因為篇幅順序的關係，這邊就先講解它給的一些提示。

1. Going through some test cases will save you time.

我們一開始在解題的時候，可能寫完之後就直接執行了，並不太會自己列許多測案來驗證，這點在鏈結陣列尤其明顯，因為它確實不怎麼容易除錯，所以它第一個提示是說，【多用一些測試案例可以節省你的時間】。

2. Feel free to use several pointers at the same time.

上一個篇章有介紹到雙指針演算法，【如果有需要，也可以使用三指針、四指針或是更多指針】，不過每個指針的命名最好是跟要追蹤的問題有關，不然除錯起來也會很麻煩。

3. In many cases, you need to track the previous node of the current node.

在單向鏈結陣列中，我們沒辦法往前尋找已經看過的節點，【有些題目的解法並不只要存取目前的節點，也需要存取前一個節點】。

小結

在反轉鏈結陣列所用到的概念，同時也是許多鏈結陣列問題的基礎，在面試時候也很常遇到相關的問題，所以至少要學會幾種鏈結陣列的解法。