Build a list that keeps its values in input order.
What to build
A list with a tail pointer, so that adding at the end is quick.
Requirements
- Add each number to the end of the list.
- Print the values in order, separated by single spaces, or
empty. - Free every node.
Input
The first line has n. The second line has n whole numbers.
Output
One line.
Constraints
n is from 0 to 1000. When n is 0, the second line is empty.
Example
Input:
3
1 2 3
Output:
1 2 3
Why it works
Without a tail pointer, each addition would have to walk the whole list. Remembering the last node makes each addition one step.
Examples
Example 1 · Input
3 1 2 3
Expected output
1 2 3
Example 2 · Input
0
Expected output
empty
Hints
Hint 1
Keep a pointer to the last node as well as the first.
Hint 2
An empty list is a special case, because head has to change.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <stdlib.h>
struct node {
int value;
struct node *next;
};
int main(void) {
int n;
scanf("%d", &n);
struct node *head = NULL, *tail = NULL;
for (int i = 0; i < n; i++) {
struct node *new_node = malloc(sizeof(struct node));
scanf("%d", &new_node->value);
new_node->next = NULL;
if (head == NULL) {
head = new_node;
} else {
tail->next = new_node;
}
tail = new_node;
}
if (head == NULL) {
printf("empty\n");
}
for (struct node *p = head; p != NULL; p = p->next) {
printf(p->next ? "%d " : "%d\n", p->value);
}
while (head != NULL) {
struct node *next = head->next;
free(head);
head = next;
}
return 0;
}