Reverse a linked list Hackerrank problem solution

Reverse a linked list Hackerrank

You’re given the pointer to the head node of a linked list. Change the next pointers of the nodes so that their order is reversed. The head pointer given may be null meaning that the initial list is empty.

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


Output Format

Change the next pointers of the nodes that their order is reversed and return the head of the reversed linked list. Do NOT print anything to stdout/console.

Sample Input

NULL
2 –> 3 –> NULL

Sample Output

NULL
3 –> 2 –> NULL
Explanation
1. Empty list remains empty
2. List is reversed from 2,3 to 3,2

Solution

To reverse a linked list, iterate through the list and change the next node to the previous node by keeping a track of the previous node for each node.

/*
  Reverse a linked list and return pointer to the head
  The input list will have at least one element  
  Node is defined as 
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
Node* Reverse(Node *head)
{
 if(head==NULL)
        return head;
    if(head->next==NULL)
    {
        return head;
    }

    struct Node* tmp= (Reverse(head->next));
    struct Node* headtmp=tmp;
    while(tmp->next!=NULL)
    {
        tmp=tmp->next;
    }
    tmp->next=head;
    head->next=NULL;
    return headtmp;
}
/*
  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;
  }
*/
    // This is a "method-only" submission. 
    // You only need to complete this method. 
Node Reverse(Node head) {
    
   if(head==null)
       return null;

    if(head.next ==null)
        {
        return head;
    }
    
    Node next=head.next;
    Node prev=null;
    Node curr=head;
    
  
    while(next!=null)
        {
          curr.next=prev;
          prev=curr; 
          curr=next;
          next=next.next;
        
    }
    
    curr.next=prev;
    return curr;
    
}
"""
 Reverse a 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):
       self.data = data
       self.next = next_node

 return back the head of the linked list in the below method.
"""

def Reverse(head):
    if head is None:
        return head
    
    last = None
    current = head
    while(current is not None):
        next_node = current.next
        current.next = last 
        last = current
        current = next_node

    return last

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.