Question

EXTRA CHALLENGE: Could you implement a merge lists function which merges n lists in order? This function would accept a pointer to an array of n pointers, where each pointer refers to a list.

Answer 1

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

struct node {
int data;
int key;
struct node *next;
};

struct node *head = NULL;
struct node *current = NULL;

//display the list
void printList() {
struct node *ptr = head;
printf("\n[ ");
  
//start from the first
while(ptr != NULL) {
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
  
printf(" ]");
}

//insert link at the first location
void insertFirst(int key, int data) {
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
  
link->key = key;
link->data = data;
  
//point it to old first node
link->next = head;
  
//point first to new first node
head = link;
}

//checking whether list is empty
bool isEmpty() {
return head == NULL;
}

int length() {
int length = 0;
struct node *current;
  
for(current = head; current != NULL; current = current->next) {
length++;
}
  
return length;
}

void sort() {

int i, j, k, tempKey, tempData;
struct node *current;
struct node *next;
  
int size = length();
k = size ;
  
for ( i = 0 ; i < size - 1 ; i++, k-- ) {
current = head;
next = head->next;
      
for ( j = 1 ; j < k ; j++ ) {   

if ( current->data > next->data ) {
tempData = current->data;
current->data = next->data;
next->data = tempData;

tempKey = current->key;
current->key = next->key;
next->key = tempKey;
}
          
current = current->next;
next = next->next;
}
}   
}

void main() {
int a[5]={8,6,7,2,9};
int length=sizeof(a)/sizeof(int);
for(int i=0;i<length;i++)
insertFirst(i,a[i]);

printf("Original List: ");
printf("Length",%d);
  
//print the list
printList();

printf("\n");
sort();
  
printf("Sorted List : ");
printList();
  

}