Jun 122012
 

Given a Singly linked list, write an iterative (non-recursive) function to reverse the linked list.

Solution:

Popular function to reverse the linked list is recursive, but as I said earlier that recursion comes with its costs. so its always better to recursive functions because of time and space complexities.

Below is the function to reverse a linked list

This function uses three pointers a, b and ptr. At any point in the while loop

ptr – points to the original list.
a – points to the intermediate node (which is moving from the original list to reversed list)
b – points to the reversed list

We will be breaking one node at a time from the given linked list (starting from first node). at any time we will be having one pointer pointing to the current list (ptr), one pointer pointing to the reversed intermediate list (b) and one pointer to break node from ptr and append to list pointed to by b.

We will be removing nodes from ptr and will be adding them to b. One node at a time

Node * reverse( Node * ptr ) 
{ 
    Node * a; 
    Node * b = NULL; 

    while(ptr != NULL) 
    { 
        a = ptr->next; 
        ptr->next = b; 
        b = ptr; 
        ptr = a; 
    }

    return b; 
}

 

  One Response to “Reversing a Singly Linked list”

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)