LeetCode Hot 100 P206 Reverse Linked List

---

Timeline

Timeline

2026-03-13

init

linked list

---

Problem:

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 out 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 only O(1) space complexity.

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

While traversing the linked list, change the current node’s next pointer to point to the previous node. Since a node does not have a reference to its previous node, you must store its previous node in advance. 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;
    }
};