#include #include

struct Node { int val; struct Node * next; };

struct Node *createNode(int val); void destroyNode(struct Node *p); struct Node *createRandomList(int n); void destroyList(struct Node *head); void displayList(struct Node *head); struct Node * mergesort(struct Node *head); struct Node * merge(struct Node * left, struct Node * right);

void main() { struct Node *list = createRandomList(32); printf("First unsorted: "); displayList(list); list = mergesort(list); printf("Mergesort: "); displayList(list); destroyList(list); printf(" ");

list = createRandomList(23); printf("Second unsorted: "); displayList(list); list = mergesort(list); printf("Mergesort: "); displayList(list); destroyList(list); }

struct Node * mergesort(struct Node *head) { if (head == NULL) return head; /* Base case of empty list */ if (head->next == NULL) return head; /* Base case of just one node */ struct Node * curr=head; struct Node * mid=head; /* Start of second list */ struct Node * prevmid; while (curr!=NULL) { curr = curr->next; prevmid = mid; mid = mid->next;; if (curr == NULL) break; curr = curr->next; } prevmid->next = NULL; /* Terminate first list */

head = mergesort(head); mid = mergesort(mid); return merge(head, mid); }

/* * left -> sorted linked list * right -> sorted linked list * Return merged sorted linked lisst * It doesn't work! Fix it! */ struct Node * merge(struct Node * left, struct Node * right) { if (right == NULL) return left; if (left == NULL) return right;

struct Node * last = right; for (; last->next != NULL; last=last->next);

last->next = left; return right; }

struct Node *createNode(int val) { struct Node *p = (struct Node *) malloc(sizeof(struct Node)); p->val = val; p->next = NULL; return p; }

void destroyNode(struct Node *p) { free(p); }

struct Node *createRandomList(int n) { srand48(1); if (n next = createNode(lrand48()%1000); last = last->next; } return head; }

void destroyList(struct Node *head) { struct Node *curr=head; struct Node *p; while (curr!=NULL) { p =curr; curr=curr->next; destroyNode(p); } }

void displayList(struct Node *head) { printf("List: "); for (struct Node *curr=head; curr!=NULL; curr=curr->next) { printf("-> %d",curr->val); } printf(" "); }

Problem 3 [2 pts]. Attached is a program merge.c. It is an implementation of mergesort, where the input is in a linked list. The output is a linked list is a sorted version of the input, where the output has increasing values. The function of mergesort is "mergesort()". It calls a function "merge()" which has as input two sorted linked lists. It merges the two linked list into a single linked list that is sorted. Note that this implementation is the top-down approach rather than the bottom-up approach discussed in class. The function "merge()" is incorrect. Your task is to write a correct version. Do not change any of the other functions. Do not copy nodes