206. Reverse Linked List - 邏輯轉換有點障礙

題目連結

這題目標很明確，反轉Linked List，初始的想法是一個一個node看，然後倒著裝就行了，馬上寫完後Time Limit Exceeded (TLE)。

TLE的Code

	class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode prev = null, curr = head;
        
        // Iterate through the list
        while (curr != null) {
            ListNode nxt = curr.next; // Original next one
            curr.next = prev; // Point in reverse direction
            prev = curr; // Current node become the previous for the next round
            curr = nxt; // Original next one becomes the current node
        }

        return prev; // Return the Last node
    }
}

看了一下Neetcode的影片

邏輯上沒什麼問題，都是嘗試把指針換邊，但他多了一個變量，應該是我換邊的邏輯有誤，導致無限迴圈。以下正解

Code

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode prev = null, curr = head;
        
        // Iterate through the list
        while (curr != null) {
            ListNode nxt = curr.next; // Original next one
            curr.next = prev; // Point in reverse direction
            prev = curr; // Current node become the previous for the next round
            curr = nxt; // Original next one becomes the current node
        }

        return prev; // Return the Last node
    }
}

這題左右轉換讓我的腦袋轉不過來，理解code的時候花了一些時間才懂，還是看到這個LC評論才更清晰

這個解釋我一看就懂了，最核心的部分就是，把每個Node的previous node放到Node的Next，沒了就這樣。遞迴也是一樣的道理，把next存下來，然後把node.next換成prev，如此一來就換邊了，然後再用原本的next call自己。

感覺兩周後來看應該還是會卡住，不過沒關係，你會懂的😭