Join the social network of Tech Nerds, increase skill rank, get work, manage projects...
 
  • Reverse a Singly Linked List in linear order of time

    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 0
    • 510
    Comment on it

    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)

Sign In
                           OR                           
                           OR                           
Register

Sign up using

                           OR                           
Forgot Password
Fill out the form below and instructions to reset your password will be emailed to you:
Reset Password
Fill out the form below and reset your password: