Given a Linked List and a number n, write a function that returns the value at the n’th node from end of the Linked List.
For example, if input is below list and n = 3, then output is “B”
Method 1 (Use length of linked list)
1) Calculate the length of Linked List. Let the length be len.
2) Print the (len – n + 1)th node from the begining of the Linked List.
C
// Simple C program to find n'th node from end #include<stdio.h> #include<stdlib.h> /* Link list node */ struct Node { int data; struct Node* next; }; /* Function to get the nth node from the last of a linked list*/ void printNthFromLast( struct Node* head, int n) { int len = 0, i; struct Node *temp = head; // 1) count the number of nodes in Linked List while (temp != NULL) { temp = temp->next; len++; } // check if value of n is not more than length of the linked list if (len < n) return ; temp = head; // 2) get the (len-n+1)th node from the begining for (i = 1; i < len-n+1; i++) temp = temp->next; printf ( "%d" , temp->data); return ; } void push( struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Drier program to test above function*/ int main() { /* Start with the empty list */ struct Node* head = NULL; // create linked 35->15->4->20 push(&head, 20); push(&head, 4); push(&head, 15); push(&head, 35); printNthFromLast(head, 4); return 0; } |
Java
// Simple Java program to find n'th node from end of linked list class LinkedList { Node head; // head of the list /* Linked List node */ class Node { int data; Node next; Node( int d) { data = d; next = null ; } } /* Function to get the nth node from the last of a linked list */ void printNthFromLast( int n) { int len = 0 ; Node temp = head; // 1) count the number of nodes in Linked List while (temp != null ) { temp = temp.next; len++; } // check if value of n is not more than length of // the linked list if (len < n) return ; temp = head; // 2) get the (len-n+1)th node from the begining for ( int i = 1 ; i < len-n+ 1 ; i++) temp = temp.next; System.out.println(temp.data); } /* Inserts a new Node at front of the list. */ public void push( int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; } /*Drier program to test above methods */ public static void main(String [] args) { LinkedList llist = new LinkedList(); llist.push( 20 ); llist.push( 4 ); llist.push( 15 ); llist.push( 35 ); llist.printNthFromLast( 4 ); } } // This code is contributed by Rajat Mishra |
Python3
# Simple Python3 program to find # n'th node from end class Node: def __init__( self , new_data): self .data = new_data self . next = None class LinkedList: def __init__( self ): self .head = None # createNode and and make linked list def push( self , new_data): new_node = Node(new_data) new_node. next = self .head self .head = new_node # Function to get the nth node from # the last of a linked list def printNthFromLast( self , n): temp = self .head # used temp variable length = 0 while temp is not None : temp = temp. next length + = 1 # print count if n > length: # if entered location is greater # than length of linked list print ( 'Location is greater than the' + ' length of LinkedList' ) return temp = self .head for i in range ( 0 , length - n): temp = temp. next print (temp.data) # Driver Code llist = LinkedList() llist.push( 20 ) llist.push( 4 ) llist.push( 15 ) llist.push( 35 ) llist.printNthFromLast( 4 ) # This code is contributed by Yogesh Joshi |
Output:
35
Following is a recursive C code for the same method. Thanks to Anuj Bansal for providing following code.
void printNthFromLast( struct Node* head, int n) { static int i = 0; if (head == NULL) return ; printNthFromLast(head->next, n); if (++i == n) printf ( "%d" , head->data); } |
Time Complexity: O(n) where n is the length of linked list.
Method 2 (Use two pointers)
Maintain two pointers – reference pointer and main pointer. Initialize both reference and main pointers to head. First move reference pointer to n nodes from head. Now move both pointers one by one until reference pointer reaches end. Now main pointer will point to nth node from the end. Return main pointer.
Implementation:
C
// C program to find n'th node from end using slow and // fast pointers #include<stdio.h> #include<stdlib.h> /* Link list node */ struct Node { int data; struct Node* next; }; /* Function to get the nth node from the last of a linked list*/ void printNthFromLast( struct Node *head, int n) { struct Node *main_ptr = head; struct Node *ref_ptr = head; int count = 0; if (head != NULL) { while ( count < n ) { if (ref_ptr == NULL) { printf ( "%d is greater than the no. of " "nodes in list" , n); return ; } ref_ptr = ref_ptr->next; count++; } /* End of while*/ while (ref_ptr != NULL) { main_ptr = main_ptr->next; ref_ptr = ref_ptr->next; } printf ( "Node no. %d from last is %d " , n, main_ptr->data); } } void push( struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* Drier program to test above function*/ int main() { /* Start with the empty list */ struct Node* head = NULL; push(&head, 20); push(&head, 4); push(&head, 15); push(&head, 35); printNthFromLast(head, 4); } |
Java
// Java program to find n'th node from end using slow and // fast pointers class LinkedList { Node head; // head of the list /* Linked List node */ class Node { int data; Node next; Node( int d) { data = d; next = null ; } } /* Function to get the nth node from end of list */ void printNthFromLast( int n) { Node main_ptr = head; Node ref_ptr = head; int count = 0 ; if (head != null ) { while (count < n) { if (ref_ptr == null ) { System.out.println(n+ " is greater than the no " + " of nodes in the list" ); return ; } ref_ptr = ref_ptr.next; count++; } while (ref_ptr != null ) { main_ptr = main_ptr.next; ref_ptr = ref_ptr.next; } System.out.println( "Node no. " +n+ " from last is " + main_ptr.data); } } /* Inserts a new Node at front of the list. */ public void push( int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; } /*Drier program to test above methods */ public static void main(String [] args) { LinkedList llist = new LinkedList(); llist.push( 20 ); llist.push( 4 ); llist.push( 15 ); llist.push( 35 ); llist.printNthFromLast( 4 ); } } // This code is contributed by Rajat Mishra |
Python
# Python program to find n'th node from end using slow # and fast pointer # Node class class Node: # Constructor to initialize the node object def __init__( self , data): self .data = data self . next = None class LinkedList: # Function to initialize head def __init__( self ): self .head = None # Function to insert a new node at the beginning def push( self , new_data): new_node = Node(new_data) new_node. next = self .head self .head = new_node def printNthFromLast( self , n): main_ptr = self .head ref_ptr = self .head count = 0 if ( self .head is not None ): while (count < n ): if (ref_ptr is None ): print "%d is greater than the no. pf nodes in list" % (n) return ref_ptr = ref_ptr. next count + = 1 while (ref_ptr is not None ): main_ptr = main_ptr. next ref_ptr = ref_ptr. next print "Node no. %d from last is %d " % (n, main_ptr.data) # Driver program to test above function llist = LinkedList() llist.push( 20 ) llist.push( 4 ) llist.push( 15 ) llist.push( 35 ) llist.printNthFromLast( 4 ) # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
Output:
Node no. 4 from last is 35
Time Complexity: O(n) where n is the length of linked list.
Please write comments if you find the above codes/algorithms incorrect, or find other ways to solve the same problem.
leave a comment
0 Comments