Reverse a Linked List
October 3, 2024·Johnathan Jacobs
Problem: Reverse a Linked list!
Solution: Store the previous
and next
pointers, as well as a current
pointer.
Each iteration, we swap current->next
to point to previous
, where next
is
used to temporarily store the original current->next
to set current
to.
Why: This uses no additional space, and does the swap in a single pass.
#include <memory>
struct LinkedNode{
ListNode* next = nullptr;
};
[[nodiscard]] ListNode* reverseLinkedList(ListNode* head) {
if(head == nullptr || head->next == nullptr) return head;
ListNode* prev = nullptr;
auto current = head;
while (current != nullptr) {
const auto next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}
int main() {
auto n3 = std::make_unique<ListNode>();
auto n2 = std::make_unique<ListNode>(n3.get());
auto n1 = std::make_unique<ListNode>(n2.get());
auto head = std::make_unique<ListNode>(n1.get());
return reverseLinkedList(head.get()) == n3.get();
}