Reverse A Linked List
November 12, 2019
We’ve done this before, but I saw questions asked about this task on three different beginner-programming forums this weekend (it must that that time in the semester when teachers introduce linked lists), and it never hurts to do some basic drill.
Your task is to write a program that reverses a linked list. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
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; } }