50141. Merge Link Lists

I'm a slow walker, but I never walk backwards.

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.

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 list 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. Note that you need to relink the lists instead of making a new one. That is, you need to change the linkage among these nodes without asking more storage. Also note that some list may be empty from the beginning in the last subtask.

exampleexample

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;
}

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.

Hints

You may use the pointer array parameter to keep track of where you have processes in each linked list. Also you need to remember the last node from the previous iteration so that you can link it to the first node in this iteration.

Subtask

  • 10 points: $K=2$. The two linked lists have the same length.
  • 20 points: $K>2$. The $K$ linked lists have the same length.
  • 70 points: $K>2$. The $K$ linked lists may have different lengths.

Sample Input 1

2
4 20 17 9 10
4 18 12 10 12

Sample Output 1

20 18 12 17 9 10 12 10

Sample Input 2

3
5 2 2 1 1 2
5 0 1 7 0 1
5 1 8 9 1 0

Sample Output 2

2 0 1 8 1 2 1 7 9 1 0 1 2 1 0

Sample Input 3

4
2 2 7
5 0 1 9 12 10
2 1 2
3 8 1 10

Sample Output 3

2 0 1 8 1 2 1 7 9 10 12 10

Discussion