Task Description
Write a program to merge several link lists into a single one. You are given the starting address of $K$ linked lists that are indexed from 0 to $K-1$. You will take $N$ iteration to merge the lists where $N$ is the length of the longest list.
You need to merge lists just like in the previous task when the flag ZIGZAG is set. In the first iteration, we link the first nodes (if they exist) from all lists in increasing index order. Please refer to the following figure for an illustration. In the second iteration we link the second nodes (if they exist) from all lists in decreasing index order, and put them after the list we constructed from the first iteration. The third iteration is just like the first iteration, and so on. Note that if a list does not have a node in an iteration, it is simply skipped in the construction. There will be $N$ iterations since there the length of the longest list is $N$. Finally we will get only one list.
Now we describe how to merge lists when the flag TOPDOWN is set. In every iteration we always link the nodes (if they exist) from all lists in increasing index order. Please refer to the following figure for an illustration.
Now we describe how to merge lists when the flag BOTTOMUP is set. In every iteration we always link the nodes (if they exist) from all lists in decreasing index order. Please refer to the following figure for an illustration.
The linked list node and the function you need to implement is defined in merge.h
.
#ifndef MERGE_H
#define MERGE_H
typedef
struct
node {
int
data;
struct
node *next;
}Node;
Node *merge(Node *list[],
int
K);
#endif
You may use the following main function to test your function.
#include <stdio.h>
#include <stdlib.h>
#include "merge.h"
int
main () {
int
K;
scanf
(
"%d"
, &K);
Node *list[K];
for
(
int
i = 0; i < K; i++) {
int
N;
scanf
(
"%d"
, &N);
if
(N == 0) {
list[i] = NULL;
continue
;
}
list[i] = (Node *)
malloc
(
sizeof
(Node));
scanf
(
"%d"
, &(list[i]->data));
list[i]->next = NULL;
Node *previous = list[i];
for
(
int
j = 1; j < N; j++) {
previous->next = (Node *)
malloc
(
sizeof
(Node));
scanf
(
"%d"
, &(previous->next->data));
previous->next->next = NULL;
previous = previous->next;
}
}
Node *result = merge(list, K);
while
(result) {
printf
(
"%d"
, result->data);
result = result->next;
printf
(
"%c"
, result ?
' '
:
'\n'
);
};
return
0;
}
Compile
gcc -O2 -DZIGZAG main.c merge.c -o zigzag
gcc -O2 -DTOPDOWN main.c merge.c -o topdown
gcc -O2 -DBOTTOMUP main.c merge.c -o bottomup
Input Format
The input contains only one test case. The first line contains $K$, the number of linked lists you need to merge. In the following $K$ lines, the first integer $N$ is the number of nodes in that list and the following $N$ integers are the values of nodes in that list.
Output Format
Visit the merged linked list and print the value of each node in one line.
Subtask
- 40 points: The flag ZIGZAG is set.
- 30 points: The flag TOPDOWN is set.
- 30 points: The flag BOTTOMUP is set.
Sample Input 1
Compile with gcc -std=c99 -O2 -DZIGZAG main.c merge.c -o zigzag
.
4
2 2 7
5 0 1 9 12 10
2 1 2
3 8 1 10
Sample Output 1
2 0 1 8 1 2 1 7 9 10 12 10
Sample Input 2
Compile with gcc -std=c99 -O2 -DTOPDOWN main.c merge.c -o topdown
.
4
2 2 7
5 0 1 9 12 10
2 1 2
3 8 1 10
Sample Output 2
2 0 1 8 7 1 2 1 9 10 12 10
Sample Input 3
Compile with gcc -std=c99 -O2 -DBOTTOMUP main.c merge.c -o bottomup
.
4
2 2 7
5 0 1 9 12 10
2 1 2
3 8 1 10
Sample Output 3
8 1 0 2 1 2 1 7 10 9 12 10