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;
    }
  }
  va_end(argp);
  return list_start;
}

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

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

  assert_lists_eq(
    reverse_list(mk_list(0)), 
                 mk_list(0));

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

This page copyright James Fisher 2020. Content is not associated with my employer. Found an error? Edit this page.

Jim Fisher

CV

Speaking

Blogroll

RSS

TigYog

Kickabout