題目描述：

反轉(zhuǎn)一個(gè)單鏈表。

示例:
輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

解題思路1:

最簡(jiǎn)單的方法當(dāng)然是使用棧來(lái)存儲(chǔ)鏈表上的一個(gè)個(gè)節(jié)點(diǎn)，再出棧將節(jié)點(diǎn)連接起來(lái)即可；

代碼1:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head)
            return nullptr;
        stack<ListNode *> tempStack;
        ListNode * res;
        while(head)
        {
            tempStack.push(head);
            head = head->next;
        }
        res = tempStack.top();
        tempStack.pop();
        ListNode *p = res;
        while(!tempStack.empty())
        {
            p->next = tempStack.top();
            tempStack.pop();
            p=p->next;
        }
        p->next = nullptr;
        return res;
    }
};

解題思路2: 迭代

遍歷鏈表，將當(dāng)前節(jié)點(diǎn)的next指向前一個(gè)元素，但要注意用一個(gè)臨時(shí)節(jié)點(diǎn)保存當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)；

代碼2:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode * prev = nullptr;
        ListNode * curr = head;
        while(curr)
        {
            ListNode * nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
};