剑指 Offer 24 反转链表

    
        标签：
        
            剑指 Offer
        
    发布于：2022-02-23 15:21:23
    编辑于：2022-02-23 16:06:35
    浏览量：753

概述

https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

https://leetcode.com/problems/reverse-linked-list/

这道题需要注意，多刷几遍，我不知道为啥我刚刚做这道题的时候竟然卡了，我的天呀。

迭代法

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prv = nullptr;
        ListNode* cur = head;
        ListNode* nxt = nullptr;
        while (cur) {
            nxt = cur->next;
            cur->next = prv;
            prv = cur;
            cur = nxt;
        }
        return prv;
    }
};

递归法

递归写法首先明确递归函数返回什么，显然这里我们需要返回新的头。

然后处理好 basecase，之后自然发现我们需要原本的前一个节点。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return helper(head, nullptr);
    }

    ListNode* helper(ListNode* head, ListNode* tail) {
        if (!head) return nullptr;
        auto* newHead = head;
        if (head->next) {
            newHead = helper(head->next, head);
        }
        head->next = tail;
        return newHead;
    }
};

递归法（不需要额外定义函数）

下面的实现中务必注意，head->next = nullptr; ，如果没有这一行，我们的输出链表的最后将有个环，进而导致 heap-use-after-free 报错。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head) return nullptr;
        auto tail = head->next;
        if (!tail) return head;
        auto ans = reverseList(head->next);
        tail->next = head;
        head->next = nullptr;
        return ans;
    }
};

Links: sword-offer-24