Leetcode 206.反转链表【C++】

地址：https://leetcode-cn.com/problems/reverse-linked-list/

题目

反转一个单链表。

示例:

输入: 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) {}
 * };
 */

#include<stack>

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        stack<int> s;//用于临时存储链表元素
        ListNode* ptr = head;
        //将链表元素依次压入栈中
        while(ptr!=NULL){
            s.push(ptr->val);
            ptr = ptr->next;
        }
        //将栈中元素依次取出并写回链表
        ptr = head;
        while(!s.empty()){
            ptr->val = s.top();
            s.pop();
            ptr = ptr->next;
        }
        return head;
    }
};