[LeetCode 解題筆記] Reverse Linked List

LeetCode 原題網址:206. Reverse Linked List

題目敘述

反轉 Linked List,假設 input 是 1->2->3->4->5->NULL,就將它反轉成 5->4->3->2->1->NULL

解法

prev 這個 pointer 指向「上次結果」的第一個節點。每次迴圈都把當前節點抓出來,把當前節點的 next 欄位指向 prev,之後再把 prev 設為當前節點。

白話文解釋這個程式的運作就是:把當前節點變成「上次結果」的第一個節點。

prev 的初始值必須設成 NULL,為什麼應該不難理解。

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    
    while (head) {
        struct ListNode* currentNode = head;
        head = head->next;
        currentNode->next = prev;
        prev = currentNode;
    }
    return prev;
}

這個解法不需要分配額外空間。

還有一種解法是遞迴的解法,可以參考官方解答

comments powered by Disqus
分享至 Facebook 分享至 Google +