Learn more about Russian war crimes in Ukraine.

How to reverse a linked list

To reverse a linked list, think of it as a stack. Repeatedly pop an item off the stack, then push it onto a second stack. The second stack will accumulate a reversed list of items.

Here’s an implementation in C:

#include <stdlib.h>
#include <stdarg.h>
#include <assert.h>

typedef struct Node {
  int val;
  struct Node * next;
} Node;

Node* pop(Node** list) {
  Node* head = *list;
  if (head == NULL) return NULL;
  *list = head->next;
  return head;

void push(Node* head, Node** list) {
  head->next = *list;
  *list = head;

Node* reverse_list(Node* head) {
  Node* reversed = NULL;
  Node* node;
  while ((node = pop(&head))) push(node, &reversed);
  return reversed;

// ----------------------------------------------------
// --------------------- TESTS ------------------------

Node* mk_node(int val, Node* next) {
  Node* node = malloc(sizeof(Node));
  node->val = val;
  node->next = next;
  return node;

void assert_lists_eq(Node* actual, Node* expected) {
  while (actual != NULL) {
    assert(expected != NULL);
    assert(actual->val == expected->val);
    actual = actual->next;
    expected = expected->next;
  assert(expected == NULL);

Node* mk_list(int len, ...) {
  Node* list_start = NULL;
  Node* list_end = NULL;
  va_list argp;
  va_start(argp, len);
  for (int i = 0; i < len; i++) {
    Node* node = mk_node(va_arg(argp, int), NULL);
    if (list_start == NULL) {
      list_start = node;
      list_end = node;
    } else {
      list_end->next = node;
      list_end = node;
  return list_start;

int main(int argc, char** argv) {
    reverse_list(mk_list(5,    1,2,3,4,5)), 
                 mk_list(5,    5,4,3,2,1));

    reverse_list(mk_list(1,    42)), 
                 mk_list(1,    42));


  return 0;

And here’s a version that does the pointer manipulation directly, without calling out to pop and push functions:

Node* reverse_list(Node* head) {
  Node* reversed_head = NULL;
  while (head != NULL) {
    Node* next = head->next;
    head->next = reversed_head;
    reversed_head = head;
    head = next;
  return reversed_head;

What can computers do? What are the limits of mathematics? And just how busy can a busy beaver be? This year, I’m writing Busy Beavers, a unique interactive book on computability theory. You and I will take a practical and modern approach to answering these questions — or at least learning why some questions are unanswerable!

It’s only $19, and you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

After months of secret toil, I and Andrew Carr released Everyday Data Science, a unique interactive online course! You’ll make the perfect glass of lemonade using Thompson sampling. You’ll lose weight with differential equations. And you might just qualify for the Olympics with a bit of statistics!

It’s $29, but you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

More by Jim

Tagged #programming, #c. All content copyright James Fisher 2020. This post is not associated with my employer. Found an error? Edit this page.