You can reverse a Singly Linked List in linear order of time by implementing the following iterative approach, there are other recursive approaches are also available. But for the sake of simplicity I am implementing the iterative approach only, as the time complexity for both of them is almost similar.
Sample code for reversing the linked list
#include <stdio.h>
#include <stdlib.h>
struct node {
char ch;
struct node *next;
};
typedef struct node node;
node * create(char c)
{
node * ptr = (node*)malloc(sizeof(node));
ptr->ch = c;
ptr->next = NULL;
return ptr;
}
void print(node *ptr)
{
while(ptr->next) {
printf("%c->",ptr->ch);
ptr = ptr->next;
}
printf("%c\n",ptr->ch);
return;
}
node * reverse_list(node *ptr)
{
node *prev = NULL;
node *hold = NULL;
while (ptr->next) {
hold = ptr->next;
ptr->next = prev;
prev = ptr;
ptr = hold;
}
ptr->next = prev;
return ptr;
}
int main()
{
node *root = NULL;
root = create('F');
root->next = create('I');
root->next->next = create('N');
root->next->next->next = create('D');
root->next->next->next->next= create('N');
root->next->next->next->next->next= create('E');
root->next->next->next->next->next->next = create('R');
root->next->next->next->next->next->next->next = create('D');
printf("Before Reverse : ");
print(root);
root = reverse_list(root); //calling the reverse root function
printf("After Reverse : ");
print(root);
return 0;
}
Output of the above code
Before Reverse : F->I->N->D->N->E->R->D
After Reverse : D->R->E->N->D->N->I->F
The time complexity of the above code is linear.
0 Comment(s)