Advertisement
imashutosh51

Nth node from end of linked list

Aug 10th, 2022 (edited)
260
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.89 KB | None | 0 0
  1. /*
  2. Method 1:find length then do len-n and print (len-n)th node
  3.          T.C O(n) but two pass S.C O(1)
  4. Mthod 2:use recursion T.C O(n), S.C O(n) due to stack of recursion calls
  5. Method 3: use two pointers
  6.     first make two pointer.keep first pointer at head and
  7.     move second pointer to nth node.Now first pointer is
  8.     nth left of second pointer.now move both pointer one
  9.     step at a time until second reaches at end.
  10.     still first pointer will be nth left of second pointer
  11.     and end of linkedlist also.
  12.     T.C O(n) two pass but one pass is not full linked list,S.C O(1)
  13. */
  14. int getNthFromLast(Node *head, int n){
  15.        Node *first=head,*second=head;
  16.        while(second && --n){
  17.            second=second->next;
  18.        }
  19.        if(n) return -1;
  20.        while(second->next){
  21.            first=first->next;
  22.            second=second->next;
  23.        }
  24.        return first->data;
  25. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement