LeetCode 206 Reverse Linked List

标签: 链表问题 LeetCode 发布于:2022-02-05 19:00:25 编辑于:2022-02-05 19:25:46 浏览量:835

题目分析

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; 即可。

未经允许,禁止转载,本文源站链接:https://iamazing.cn/