LeetCode 206. Reverse Linked List [Easy] [C++] 解題筆記

這題要求我們反轉一個 Single Linked List.

EX:

        Input: 1->2->3->4->5->NULL

        Output: 5->4->3->2->1->NULL

想法:

        這題基本上就照著做把目前的 node 指向前一個 node 即可。

完整程式碼:

解法一 (iterative):

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        auto cur = head;
        ListNode* prev = NULL;
        while (cur != NULL) {
            auto tmp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = tmp;
        }   
            
        return prev;
    }   
};

解法二(recursive):

class Solution {
public:
    ListNode* reverse(ListNode* cur, ListNode* prev) {
        if (cur == NULL) { return prev; }
        auto tmp = cur->next;
        cur->next = prev;
        return reverse(tmp, cur);
    }
    ListNode* reverseList(ListNode* head) {
        return reverse(head, NULL);
    }
};