LeetCode 206 Reverse Linked List

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

题目分析

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

Links: leetcode-206-reverse-linked-list