Reverse a Linked List

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 O(n)O(n) 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();
}