How can you take a linked list and reverse it? This is a classic data structures
ID: 3585525 • 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. Your algorithm should complete in linear time and should not require you to build a second list. All programs must include a comment section at the top of the program as outlined below Progra Author Date: Time spent: total amount of time spent on the project Purpose The purpose of this program is to blah blah blahExplanation / Answer
/************************************************************
Program : Reversing a linked list
Author : <your name>
Date : 10/03/2017
Time spent : 30 minutes
Purpose : The purpose of this program is to reverse a given linked list .
************************************************************/
#include<stdio.h>
#include<stdlib.h>
struct node;
typedef struct node Node;
/* Link list node */
struct Node
{
int data;
Node* next;
};
/* Function to reverse the linked list */
static void reverse(struct Node** head_ref)
{
Node* prev = NULL;
Node* current = *head_ref;
Node* next;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
/* Function to print linked list */
void printList(struct Node *head)
{
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 */
Node* head = NULL;
int i;
Node* temp;
//set up a test list with values 9->8->7->...->0
for(i=0;i<10;i++)
{
temp = (Node*)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
reverse(&head);
//print the reversed list.
printf("Reversed linked list ");
printList(head);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.