Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Method 1:find length then do len-n and print (len-n)th node
- T.C O(n) but two pass S.C O(1)
- Mthod 2:use recursion T.C O(n), S.C O(n) due to stack of recursion calls
- Method 3: use two pointers
- first make two pointer.keep first pointer at head and
- move second pointer to nth node.Now first pointer is
- nth left of second pointer.now move both pointer one
- step at a time until second reaches at end.
- still first pointer will be nth left of second pointer
- and end of linkedlist also.
- T.C O(n) two pass but one pass is not full linked list,S.C O(1)
- */
- int getNthFromLast(Node *head, int n){
- Node *first=head,*second=head;
- while(second && --n){
- second=second->next;
- }
- if(n) return -1;
- while(second->next){
- first=first->next;
- second=second->next;
- }
- return first->data;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement