50146. Merge Link Lists, Again

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.

example

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.

example

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.

example

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