【LeetCode】反转链表

题目描述：

反转一个单链表。

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

解题思路1:

最简单的方法当然是使用栈来存储链表上的一个个节点，再出栈将节点连接起来即可；

代码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: 迭代

遍历链表，将当前节点的next指向前一个元素，但要注意用一个临时节点保存当前节点的下一个节点；

代码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;
    }
};