Jul 012015
 

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

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)