定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
?限制：
0 <= 节点个数 <= 5000
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。?
第一种思路就是遍历我们的链表，并且将我们链表中的数据压入我们的栈中。
第一次遍历完之后，我们再次从头遍历我们的链表，将我们的数据从栈中取出，放入我们链表的结点中，这样就将我们链表中的数据成功逆置了。?
/**
* 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* tmp=head;
stack<int> st1;
while(tmp!=nullptr)
{
st1.push(tmp->val);
tmp=tmp->next;
}
tmp=head;
while(tmp!=nullptr)
{
tmp->val=st1.top();
st1.pop();
tmp=tmp->next;
}
return head;
}
};
这里我们看到由于我们遍历了两遍链表，并且使用了stack，所以我们的执行时间和内存消耗都没有特别优秀?
这个时候我们可以考虑使用第二种方法，就是在遍历链表的同时，将链表逆置。?
?
这里我们需要注意的是在代码初始的时候要判断tmp是否为nullptr，因为测试用例中有[]
有了tmp不是nullptr，还要判断pre是否为nullptr，因为测试用例中有[1]
然后我们迭代最终的循环结束可以pre->next==nullptr为终点
然后将链表的最后一个结点反转，返回pre即可?
/**
* 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* tmp=head;
if(tmp==nullptr)
{
return head;
}
ListNode*pre=head->next;
if(pre==nullptr)
{
return head;
}
tmp->next=nullptr;
while(pre->next!=nullptr)
{
ListNode* pre_pre=pre->next;
pre->next=tmp;
tmp=pre;
pre=pre_pre;
}
pre->next=tmp;
return pre;
}
};
?
?