MUST BE WRITTEN IN C PROGRAMMING AND TAKE SCREENSHOT! /************* structs and typedefs *************/ typedef struct node { ElemType val; struct node *next; } NODE; struct list_struct { NODE *front; NODE *back; }; /************* structs and typedefs *************/ /* * returns pointer to newly created empty list */ LIST *lst_create() { LIST *l = malloc(sizeof(LIST)); l->front = NULL; l->back = NULL; return l; } LIST * lst_from_array(ElemType a[], int n) { int i; LIST *lst; lst = lst_create(); for(i=n-1; i>=0; i--) lst_push_front(lst, a[i]); return lst; } /** 

THE ABOVE TEXT IS FROM HEADER FILE ^^ /** TODO * function: lst_merge_sorted * * description: assumes both list a and b are in * sorted (non-descending) order and merges them * into a single sorted list with the same * elements. * * This single sorted list is stored in a while * b becomes empty. * * if either of given lists are not sorted, * we blame the caller and the behavior is * implementation dependent -- i.e., don't worry * about it! * * Example: * * a: [2 3 4 9 10 30] * b: [5 8 8 11 20 40] * * after call on (a,b) * * a: [2 3 4 5 8 8 9 10 11 20 30 40] * b: [] * * implementation: should not allocate ANY new list * nodes -- it should just re-link existing * nodes. * * Must be linear time in the |a|+|b| -- i.e., * the total number of elements being processed. * * Suggestion: consider writing a recursive helper function * that does the merge at the "NODE level"; have the * non-recursive caller clean up the details (front, back * pointers, etc). * * DIFFICULTY LEVEL: 3 */ extern void lst_merge_sorted(LIST *a, LIST *b);