原题链接
来源：剑指offer, Hulu面试题
题意很简单。给定一个单链表，反转这个单链表，返回翻转后的头节点。
方法一 借助栈的性质
要将链表翻转，很容易想到借助栈的后进先出的性质来改变链表的顺序。
将链表节点顺序压入栈中，链表节点全部进栈以后，取栈顶元素作为新链表的头节点，然后将元素不断出栈，每出栈一个元素就连接到新链表的末尾。
时间复杂度：将链表元素压入栈中需要遍历一次链表，将栈中所有元素连接起来需要遍历一遍栈，时间复杂度是O(n).
空间复杂度：需要额外开一个栈存放所有元素，空间复杂度是O(n).
代码如下：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == NULL) {
return head;
}
stack<ListNode*> st;
ListNode* cur = head; //记录当前节点
while(cur != NULL) { //只要节点非空，就压入栈中，指针后移，处理下一个节点
st.push(cur);
cur = cur -> next;
}
auto dummy = new ListNode(-1); //用一个附加头节点的next指针指向翻转后的链表的头节点，这样返回值就可以是dummy -> next
if(!st.empty()) {
cur = st.top();
dummy -> next = cur; //附加头节点的next指针指向栈顶元素
st.pop();
}
while(!st.empty()) {
cur = cur -> next = st.top(); //不断取出栈顶元素连接到新链表的末尾
st.pop();
}
cur -> next = NULL; //链表尾节点的next指针指向空
return dummy -> next;
}
};
方法二 迭代
翻转操作就是将链表中所有节点的next指针指向他们原来的前驱节点。
由于链表是单链表，只有next指针没有pre指针指向前驱节点，因此我们需要额外用一个变量pre记录每个节点的前驱节点，并且将当前节点cur
的next指针指向pre，由于改变了cur的next指针的值，但是在改变next的值之前我们还是需要记录cur的下一个节点（为了进行遍历/迭代），
所以还需要额外用一个变量next来记录节点（按原来顺序的）下一个节点。
时间复杂度：只遍历一次链表，时间复杂度是O(n).
空间复杂度：额外开了三个变量pre, cur, next,空间复杂度是O(1).
代码如下：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
while(cur != NULL) {
ListNode* next = cur -> next; //在修改cur的next指针的值之前需要记录cur的下一个节点
cur -> next = pre; //将next指针指向前驱节点
pre = cur; //pre和cur都向后移动，翻转下一个节点
cur = next;
}
return pre; //跳出上面的while循环时，cur为空，pre指向原链表的最后一个节点，也就是翻转后的链表的头节点
}
};
方法三 递归
reverseList函数的功能是给定一个链表的头节点，返回新链表的头节点（也就是原链表的尾节点），
head最开始为头节点（只有一个节点，我们可以认为已经翻转好了，只不过还没修改next指针为空），
我们可以递归处理head -> next，head -> next是当前遍历到的链表长度的尾节点（也就是加入了一个新的需要翻转的节点），
也就是新链表的头节点newHead, 这时需要先记录newHead的next指针指向head（翻转）：head -> next -> next = head;
然后head的next指针要指向空（原来指向后继结点）。
时间复杂度：链表中每个节点遍历一次，时间复杂度是O(n).
空间复杂度：总共递归n层，总共需要O(n)的空间，系统栈的空间复杂度是O(n).
代码如下：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == NULL || head -> next == NULL) {
return head;
}
ListNode* newHead = reverseList(head -> next); //递归
head -> next -> next = head;
head -> next = NULL;
return newHead;
}
};