How can you take a linked list and reverse it? This is a classic data structures
ID: 3679459 • Letter: H
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; } //Define your function here
Explanation / Answer
There are multiple ways to go about this. Let’s first look at a recursive solution.
Node * reverse( Node * ptr , Node * previous)
{
Node * temp;
if(ptr->next == NULL) {
ptr->next = previous;
return ptr;
} else {
temp = reverse(ptr->next, ptr);
ptr->next = previous;
return temp;
}
}
reversedHead = reverse(head, NULL);
Now for a non-recursive solution.
Node * reverse( Node * ptr )
{
Node * temp;
Node * previous = NULL;
while(ptr != NULL) {
temp = ptr->next;
ptr->next = previous;
previous = ptr;
ptr = temp;
}
return previous;
}
A COMPLETE ‘C’ CODE.
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct node
{
int data;
struct node* next;
};
/* Function to reverse the linked list */
static void reverse(struct node** head_ref)
{
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
/* Function to push a node */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print linked list */
void printList(struct node *head)
{
struct node *temp = head;
while(temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
}
/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;
push(&head, 20);
push(&head, 4);
push(&head, 15);
push(&head, 85);
printList(head);
reverse(&head);
printf(" Reversed Linked list ");
printList(head);
getchar();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.