How can you take a linked list and reverse it? This is a classic data structures

Question

How can you take a linked list and reverse it? This is a classic data structures question for interview candidates and so I want you to give it a try. Take the given starter code listed with this assignment and add in the code needed to reverse the linked list. You should not require you to build a second list #include #include struct node; typedef struct node Node, * Node_Ptr; typedef int Item; struct node { Item data; Node_Ptr next; }; //declare your function here. int main(int argc, char* argv[]) { Node_Ptr head = NULL; int i; Node_Ptr temp; //set up a test list with values 9->8->7->...->0 for (i = 0; i < 10; i++) { temp = (Node_Ptr)malloc(sizeof(Node)); if (temp == NULL) { printf("out of memory? "); exit(1); } temp->data = i; temp->next = head; head = temp; } //call your function to reverse the list (should work for any list given the head node). //print the reversed list. temp = head; while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; } return 0; }

Explanation / Answer

#include typedef struct Node { char data; struct Node* next; } Node; void print_list(Node* root) { while (root) { printf("%c ", root->data); root = root->next; } printf(" "); } Node* reverse(Node* root) { Node* new_root = 0; while (root) { Node* next = root->next; root->next = new_root; new_root = root; root = next; } return new_root; } int main() { Node d = { 'd', 0 }; Node c = { 'c', &d }; Node b = { 'b', &c }; Node a = { 'a', &b }; Node* root = &a; print_list(root); root = reverse(root); print_list(root); return 0; }

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.