Gold bar puzzle
July 1, 2015
Minimum number of platform required for a railway station
September 23, 2015

Reversing a doubly linked list

Given a doubly linked list. Write a function to reverse it. If given list is
doubly linked list
then output of our function should be
doubly linked list reverse
Solution:
Reversing a doubly linked list is simpler than reversing a Singly linked list. The logic however remains the same, but since node holds the address of both next and previous node we don’t need three extra pointers.
Below is the code for reversing doubly linked list:

// Reverses a doubly linked list and return pointer
// to the head of the reversed list.
ListNode* reverseList(ListNode* head)
{
    // If list has 0 or 1 node. don't reverse.
    if(head == NULL || head->next == NULL) { return head; }
    ListNode* a = head->next;
    head->next = NULL;
    while(a != NULL)
    {
        head->prev = a;
        ListNode * temp = a->next;
        a->next = head;
        head = a;
        a = temp;
    }
    return head;
}

Time Complexity: The function takes O(n) time.
Memory Complexity: The function takes constant amount of extra memory.
ListNode is the Node. Below is the complete program written in C++ (The ListNode struct has a constructor, hence it will not run in C language).

// Structure for node of DLL
struct ListNode
{
    ListNode* prev;
    int data;
    ListNode* next;
    // Constructor.
    ListNode(int d): prev(NULL),data(d),next(NULL){}
};
// Reverses a doubly linked list and return pointer
// to the head of the reversed list.
ListNode* reverseList(ListNode* head)
{
    // If list has 0 or 1 node. don't reverse.
    if(head == NULL || head->next == NULL) { return head; }
    ListNode* a = head->next;
    head->next = NULL;
    while(a != NULL)
    {
        head->prev = a;
        ListNode * temp = a->next;
        a->next = head;
        head = a;
        a = temp;
    }
    return head;
}
// Helper function to print the list.
void printList(ListNode* h)
{
    cout<<"List is : ";
    while(h != NULL)
    {
        cout<<h->data<<" ";
        h = h->next;
    }
    cout<<"\n";
}
int main()
{
    ListNode* h = new ListNode(1);
    h->next = new ListNode(2);
    h->next->prev = h;
    h->next->next = new ListNode(3);
    h->next->next->prev = h->next;
    printList(h);
    h = reverseList(h);
    printList(h);
}

Leave a Reply

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