leetcode热题100 P206 反转链表

---

时间轴

时间轴

2026-03-13

init

链表

---

题目：

P206 反转链表

https://leetcode.cn/problems/reverse-linked-list/description/?envType=study-plan-v2&envId=top-100-liked

用栈存储所有链表，再出栈就是反转后的链表

struct ListNode {
        int val;
        ListNode *next;
        ListNode()
                : val(0)
                , next(nullptr)
        {
        }
        ListNode(int x)
                : val(x)
                , next(nullptr)
        {
        }
        ListNode(int x, ListNode *next)
                : val(x)
                , next(next)
        {
        }
};

#include <stack>
using std::stack;

class Solution {
    public:
        ListNode *reverseList(ListNode *head)
        {
                if (head == nullptr)
                        return nullptr;                
                ListNode *p = head;

                stack<ListNode *> stk;

                while (p != nullptr) {
                        stk.push(p);
                        p = p->next;
                }

                head = stk.top();
                ListNode *last = head;
                stk.pop();

                while (!stk.empty()) {
                        p = stk.top();
                        stk.pop();
                        last->next = p;
                        last = p;
                }
                last->next = nullptr;

                return head;
        }
};

看了题解也可以指用O(1)的空间复杂度

假设链表为 1→2→3→∅，我们想要把它改成 ∅←1←2←3。

在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。

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