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

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