Leetcode 206.反转链表 迭代递归栈
原题链接:https://leetcode-cn.com/problems/reverse-linked-list/
迭代法
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
while (cur) {
ListNode* rear = cur->next;
cur->next = pre;
pre = cur;
cur = rear;
}
return pre;
}
};
递归法
- 理解递归的返回值的回溯(本节必看重点)(本人最重要的收获)
- 写递归函数应思考的
- 第一,递归的参数
- 第二,递归的停止判断
- 第三,递归的返回值(最难最重要)
class Solution {
public:
ListNode* reverse(ListNode* pre, ListNode* cur) {
if (cur == NULL) return pre;
ListNode* tmp = cur->next;
cur->next = pre;
return reverse(cur,tmp);
//理解,递归的特性,把最后函数的pre给逐级回溯回去,就是说只返回最后一个函数返回的
}
listNode* reverseList(ListNode* head) {
return reverse(NULL, head);
}
};
栈
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL) return head;
stack<ListNode*>st;
while (head != NULL) {
st.push(head);
head = head->next;
}
head = st.top();
while (!st.empty()) {
ListNode* pre = st.top();
st.pop();
pre->next = st.empty() ? NULL : st.top();
}
return head;
}
};