How to find nth element from the end of the linked list?
Or in other words Given an integer ‘n’, return a pointer to the n-th node from the end of the list.
Note: Linked list is singly linked list (there is only next pointer no previous pointer).
See Solution: find nth element from end of linked list
Keep two pointers pointer1 and pointer2, both pointing to head of the linked list initially. Increment pointer1 by one node till it reaches (n+1)th node. Now increment both pointers by one node till pointer1 becomes null. At this point the node which pointer2 is pointing to will be the nth node from the last.
Code in C/C++
Node * getNthNodeFromLast(Node * node, int n){ Node* pointer1 = node; Node* pointer2 = node; while(pointer1 != null && n > 0){ pointer1 = pointer1->next; n--; } //List does not have n nodes, so return null if(n > 0) return null; //traverse till pointer1 becomes null while(pointer1 != null){ pointer1 = pointer1->next; pointer2 = pointer2->next; } return pointer2; }
Facebook Comments