春季每日一題(3.17)反轉連結清單

35. 反轉連結清單

定義一個函數，輸入一個連結清單的頭結點，反轉該連結清單并輸出反轉後連結清單的頭結點。

思考題：

• 請同時實作疊代版本和遞歸版本。

樣例

輸入:1->2->3->4->5->NULL

輸出:5->4->3->2->1->NULL
           

題解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* p = head;//目前位置
        while(p){
            ListNode* next = p->next;
            p->next = prev;
            prev = p;
            p = next;
        }
        return prev;
    }
};
           

• 思路就是，先存下目前位置後面的，然後把目前位置的下一位指向prev前面位置，然後prev往後移到目前位置，p移到之前存的next位置