Build a doubly linked list and print it in both directions.
What to build
A doubly linked list whose prev pointers are correct enough to walk it backwards.
Requirements
- Append each number at the end of the list, setting both
prevandnext. - Print the list from the head on the first line.
- Print the list from the tail, following
prev, on the second line.
Input
The first line has n. The second line has the n numbers.
Output
Two lines: the numbers in order, then in reverse order.
Constraints
1 ≤ n ≤ 100.
Example
Input:
4
1 2 3 4
Output:
1 2 3 4
4 3 2 1
Why it works
The second line can only be right if every prev pointer is right, so printing backwards tests the half of the links that a forward walk never uses.
Examples
Example 1 · Input
4 1 2 3 4
Expected output
1 2 3 4 4 3 2 1
Example 2 · Input
1 8
Expected output
8 8
Hints
Hint 1
Each new node's prev is the old tail, and its next is NULL.
Hint 2
If there is an old tail, its next becomes the new node. Otherwise the new node is the head.
Hint 3
To print backwards, start at tail and follow prev until NULL.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int value;
struct node *prev, *next;
} Node;
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->prev = tail;
p->next = NULL;
if (tail != NULL) tail->next = p;
else head = p;
tail = p;
}
for (Node *p = head; p != NULL; p = p->next) {
if (p != head) printf(" ");
printf("%d", p->value);
}
printf("\n");
for (Node *p = tail; p != NULL; p = p->prev) {
if (p != tail) printf(" ");
printf("%d", p->value);
}
printf("\n");
while (head != NULL) {
Node *next = head->next;
free(head);
head = next;
}
return 0;
}