### 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.

Pages: 1 2

### 2 Responses to “Reverse A Linked List”

1. Daniel said

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

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
```