LeetCode 206 Reverse Linked List
题目分析
https://leetcode.com/problems/reverse-linked-list/
迭代法
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head) return nullptr;
ListNode* pre = nullptr;
ListNode* cur = head;
ListNode* nxt = head->next;
while (cur) {
nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
};
递归法
首先给出一个有问题的实现：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr) return nullptr;
auto tail = head->next;
if (tail == nullptr) return head;
auto ans = reverseList(head->next);
tail->next = head;
return ans;
}
};
提交运行后会报错：heap use after free
这是因为我们的原始 head 的 next 指针没有被纠正，导致环的出现，进而导致访问了已经被 free 的内存。
解决办法也很简单，加一行 head->next = nullptr; 即可。