C program output
June 12, 2012
Recursive function to reverse a linked list
June 12, 2012

Reversing a Singly Linked list

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;
}

 

1 Comment

  1. […] I talked about Reversing a Singly linked list without using recursion. Today let’s write a recursive function to reverse a singly linked list. Note, that […]

Leave a Reply

Your email address will not be published. Required fields are marked *