Get Node Value Hackerrank problem solution

Get Node Value Hackerrank

You’re given the pointer to the head node of a linked list and a specific position. Counting backwards from the tail node of the linked list, get the value of the node at the given position. A position of 0 corresponds to the tail, 1 corresponds to the node before the tail and so on.

Input Format

You have to complete the int GetNode(Node* head, int positionFromTail) method which takes two arguments – the head of the linked list and the position of the node from the tail. positionFromTail will be at least 0 and less than the number of nodes in the list. You should NOT read any input from stdin/console.

Constraints
Position will be a valid element in linked list.

Output Format
Find the node at the given position counting backwards from the tail. Then return the data contained in this node. Do NOT print anything to stdout/console.

Sample Input

1 -> 3 -> 5 -> 6 -> NULL, positionFromTail = 0
1 -> 3 -> 5 -> 6 -> NULL, positionFromTail = 2
Sample Output

6
3

Solution

To get the nth node from the tail of the linked list, we can calculate the length of the entire list by traversing the list once. Let this length be l. nth node from the tail is the (l-n-1)th node from the start (everything is 0-based) Or we can use two pointers. We can increment one of these to point to the nth node from the start and then increment both of these simultaneously till the first node reaches the end of the list. The second node points to the nth node from the tail.

Pseudocode:
GetNthNode(Node head, N)
ptr1=head //First Pointer
ptr2=head //Second Pointer
count=0
//Increment ptr1 till it points to Nth node from the head
while ptr1 is not NULL and countnext
count++

while ptr1->next is not NULL
ptr1=ptr1->next
ptr2=ptr2->next

//ptr2 points to the Nth node from the tail
return ptr2’s value
Statistics

/*
  Get Nth element from the end in a linked list of integers
  Number of elements in the list will always be greater than N.
  Node is defined as 
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
int GetNode(Node *head,int positionFromTail)
{
    int index = 0;
    Node* current = head;
    Node* result = head;
    while(current!=NULL)
    {
        current=current->next;
        if (index++>positionFromTail)
        {
            result=result->next;
        }
    }
    return result->data;
}
/*
  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;
  }
*/
    
int GetNode(Node head,int n) {
     // This is a "method-only" submission. 
     // You only need to complete this method. 
    
   
    
     if(head.next==null)
         return head.data;
     Node temp=head;
     int count=0;
     while(temp!=null)
         {
         count++;
         temp=temp.next;
     }
    
    int k=count-n-1;
    temp=head;
    while(k>0)
        {
        
         k--;
         temp=temp.next;
    }
    return temp.data;
    
    

}
#Body
"""
 Get Node data of the Nth Node from the end.
 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 node data of the linked list in the below method.
"""

def GetNode(head, position):
    current = head
    result = head
    index = 0
    while current is not None:
        current = current.next
        
        if index > position:
            result = result.next
        index+=1
    
    return result.data
 

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.