LeetCode Hot 100 P206 Reverse Linked List

---

Timeline

timeline

2026-03-13

init

linked list

---

Title:

P206 Reverse Linked List

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

Use a stack to store all nodes of the linked list, then popping them gives the reversed linked list.

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

After reading the solution, it can also be done with O(1) space complexity.

Assume the linked list is 1→2→3→∅, we want to change it to ∅←1←2←3.

When traversing the linked list, change the current node’s next pointer to point to the previous node. Since the node does not reference its previous node, you must store its previous node beforehand. Before changing the reference, you also need to store the next node. Finally, return the new head reference.

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