#include #include

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

void displayList(struct Node *head); struct Node * destroyList(struct Node *head); struct Node * createList(int startVal, int finishVal);

struct Node *reorderList(struct Node *head);

void main() {

struct Node *p = createList(3,13);

p = createList(3,13); printf(" Created a list: "); displayList(p); p =reorderList(p); printf("Reordered list: "); displayList(p); p = destroyList(p);

p = createList(3,12); printf(" Created a list: "); displayList(p); p =reorderList(p); printf("Reordered list: "); displayList(p); p = destroyList(p);

}

struct Node *reorderList(struct Node *head) { return head; }

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

struct Node * destroyList(struct Node *head) { struct Node *p = head; while (p!=NULL) { struct Node *next = p->next; free(p); p = next; } return NULL; }

struct Node *createList(int startVal, int finishVal) { struct Node *head = NULL; /* Head of the list */ struct Node *last = NULL; /* Last node in the list */ for (int i=startVal; ival = i; p->next = NULL; if (i == startVal) { head = p; } else { last->next = p; } last = p; } return head; }

Problem 3 [ 2 pts]. Attached with this homework is a file "reorder.c" that has the following function: struct Node * reorderList(struct Node * head); Reorders the linked list as follows and returns its head Input: L(0)>L(1)>L(2)>L(n1)>NULL Output: L(0)>L(n1)>L(1)>L(n2)>L(2)>L(n3)NULL Implement this function correctly and use O(n) time complexity and O(1) space complexity (amount of addition memory used by the function). You may not modify the data values (int val) in the nodes, only the pointer valu ('next') may be changed