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.
Programming Praxis 
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:
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; } }