Reverse a doubly linked list Hackerrank problem solution

Reverse a doubly linked list Hackerrank

You’re given the pointer to the head node of a doubly linked list. Reverse the order of the nodes in the list. The head node might be NULL to indicate that the list is empty.

Input Format
You have to complete the Node* Reverse(Node* head) method which takes one argument – the head of the doubly linked list. You should NOT read any input from stdin/console.

Output Format
Change the next and prev pointers of all the nodes so that the direction of the list is reversed. Then return the head node of the reversed list. Do NOT print anything to stdout/console.

Sample Input

NULL
NULL <-- 2 <--> 4 <--> 6 –> NULL

Sample Output

NULL
NULL <-- 6 <--> 4 <--> 2 –> NULL
Explanation
1. Empty list, so nothing to do.
2. 2,4,6 become 6,4,2 o reversing in the given doubly linked list.

Solution

All we need to do is swap prev and next pointers for all nodes, change prev of the head (or start) and change the head pointer in the end.

/*
   Reverse a doubly linked list, input list may also be empty
   Node is defined as
   struct Node
   {
     int data;
     Node *next;
     Node *prev;
   }
*/
Node* Reverse(Node* node)
{
  // If empty list, return
  if (!node) return NULL;
  
  // Otherwise, swap the next and prev
  Node *temp = node->next;
  node->next = node->prev;
  node->prev = temp;
  
  // If the prev is now NULL, the list
  // has been fully reversed
  if (!node->prev) return node;
  
  // Otherwise, keep going
  return Reverse(node->prev);
}
"""
 Reverse a doubly linked list
 head could be None as well for empty list
 Node is defined as
 
 class Node(object):
 
   def __init__(self, data=None, next_node=None, prev_node = None):
       self.data = data
       self.next = next_node
       self.prev = prev_node

 return the head node of the updated list 
"""
def Reverse(head):
    if head == None:
        return
    
    current = head
    prev = None
    
    while current != None:
        nxt = current.next
        current.prev = nxt
        current.next = prev
        prev = current
        current = nxt

    return prev
Node* Reverse(Node* head)
{
     Node *temp = NULL;  
     Node *current = head;


     while (current !=  NULL)
     {
       temp = current->prev;
       current->prev = current->next;
       current->next = temp;              
       current = current->prev;
     }      
    if(temp != NULL )
        head = temp->prev;

    return head;

}
/*
  Insert Node at the end of a linked list 
  head pointer input could be NULL as well for empty list
  Node is defined as 
  class Node {
     int data;
     Node next;
     Node prev;
  }
*/

Node Reverse(Node head) {
    
    if(head==null)
        return null;
    
    if(head.next==null)
        return head;
    
    Node temp=head;
    Node next=temp.next;
    while(next!=null)
        {
          
           temp.next=temp.prev;
        temp.prev=next;
        temp=next;
        next=next.next;
        
    }
    
    temp.next=temp.prev;
    temp.prev=null;
    return temp;

}

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.