Read n numbers and store them in a linked list, in the same order. Reverse the list by changing the next pointers (do not copy the values into an array), then print it from its new head. Free every node at the end.
What to build
A function that reverses a linked list by changing its pointers.
Requirements
- Do not copy the values into an array.
- Walk the list once, pointing each node back at the node before it.
- Free every node at the end.
Input
The first line has n (1 ≤ n ≤ 1000). The second line has the n numbers.
Output
The numbers in reverse order on one line, separated by spaces.
Constraints
1 ≤ n ≤ 1000.
Example
Input:
4
1 2 3 4
Output:
4 3 2 1
Why it works
Each next pointer is turned round to point at the previous node. Saving the old next first keeps the way forward.
Examples
4 1 2 3 4
4 3 2 1
1 42
42
Hints
Hint 1
Walk the list with three pointers: prev (starts NULL), the current node, and next.
Hint 2
For each node: save next, point the node back at prev, then move prev and the current node one step on.
Hint 3
When the walk ends, prev is the new head.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int value;
struct node *next;
} Node;
Node *reverse(Node *head) {
Node *prev = NULL;
while (head != NULL) {
Node *next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
int main(void) {
int n;
scanf("%d", &n);
Node *head = NULL, *tail = NULL;
for (int i = 0; i < n; i++) {
Node *p = malloc(sizeof(Node));
scanf("%d", &p->value);
p->next = NULL;
if (head == NULL) head = p;
else tail->next = p;
tail = p;
}
head = reverse(head);
for (Node *p = head; p != NULL; p = p->next) {
if (p != head) printf(" ");
printf("%d", p->value);
}
printf("\n");
while (head != NULL) {
Node *next = head->next;
free(head);
head = next;
}
return 0;
}