剑指 Offer 24 反转链表

Tag: 剑指-Offer Posted on 2022-02-23 15:21:23 Edited on 2022-02-23 16:06:35 Views: 158

概述

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;
    }
};

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