Reverse A Linked List

November 12, 2019

We begin with a simple list:

(define xs '(1 2 3 4 5 6 7))

Scheme provides a built-in function to reverse a list; it returns a newly-allocated list and does not modify the original list:

> (reverse xs)
(7 6 5 4 3 2 1)
> xs
(1 2 3 4 5 6 7)

We write a function rev that does the same thing as Scheme’s reverse:

(define (rev xs)
  (let loop ((xs xs) (zs (list)))
    (if (null? xs) zs
      (loop (cdr xs) (cons (car xs) zs)))))
> (rev xs)
(7 6 5 4 3 2 1)
> xs
(1 2 3 4 5 6 7)

Sometimes you want to reverse a list in-place:

(define (rev! xs)
  (let loop ((prev (list)) (curr xs))
    (if (null? curr) prev
      (let ((next (cdr curr)))
        (set-cdr! curr prev)
        (loop curr next)))))
> (set! xs (rev! xs))
> xs
(7 6 5 4  3 2 1)
> (set! xs (rev! xs))
> xs
(1 2 3 4 5 6 7)

You can run the program at https://ideone.com/Vz2Qi7.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
2 Comments »

2 Responses to “Reverse A Linked List”

  1. Daniel said
    November 14, 2019 at 3:10 AM

    Here’s a solution in C.

    #include <stdio.h>
#include <stdlib.h>

typedef struct node {
  int val;
  struct node* next;
} node_t;

void reverse(node_t** list) {
  node_t* prev = NULL;
  node_t* node = NULL;
  node_t* next = *list;
  while (next != NULL) {
    prev = node;
    node = next;
    next = next->next;
    node->next = prev;
  }
  *list = node;
}

void print_list(node_t* list) {
  while (list != NULL) {
    printf("%d", list->val);
    if (list->next != NULL)
      printf("->");
    list = list->next;
  }
  printf("\n");
}

int main(int argc, char* argv[]) {
  node_t* list = NULL;
  for (int i = argc - 1; i > 0; --i) {
    node_t* node = malloc(sizeof(node_t));
    node->val = atoi(argv[i]);
    node->next = list;
    list = node;
  }
  printf("list:\n  ");
  print_list(list);
  printf("reversed(list):\n  ");
  reverse(&list);
  print_list(list);
  while (list != NULL) {
    node_t* next = list->next;
    free(list);
    list = next;
  }
  return EXIT_SUCCESS;
}

    Example:

    $ ./a.out 1 2 3 4 5
list:
  1->2->3->4->5
reversed(list):
  5->4->3->2->1
  2. matthew said
    November 14, 2019 at 7:52 PM

    Here’s a variation on Daniel’s solution, using some C++ features. The actual in-place list reverse is neatly expressed as an iterated rotation of list elements:

    #include <stdlib.h>
#include <iostream>

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

template <typename T>
void rotate3(T &a, T &b, T &c) {
  T tmp = a; a = b; b = c; c = tmp;
}

Node *reverse(Node *node) {
  Node *prev = nullptr;
  while (node) rotate3(prev,node,node->next);
  return prev;
}

std::ostream &operator<<(std::ostream &ostr, Node *node) {
  for( ; node; node = node->next) {
    ostr << node->val << (node->next ? "->" : "");
  }
  return ostr;
}

int main(int argc, char *argv[]) {
  Node *list = nullptr;
  for (int i = argc - 1; i > 0; --i) {
    Node *node = new Node;
    node->val = atoi(argv[i]);
    node->next = list;
    list = node;
  }
  std::cout << "list: " << list << "\n";
  list = reverse(list);
  std::cout << "reversed: " << list << "\n";
  while (list) {
    Node *next = list->next;
    delete list;
    list = next;
  }
}

    $ g++ -Wall reverse.cpp -o reverse
$ ./reverse 1 2 3 4 5
list: 1->2->3->4->5
reversed: 5->4->3->2->1

Leave a comment