HOW TO GET Nth NODE FROM THE END OF A LINKED LIST

how to get Nth NODE FROM THE END OF A LINKED LIST

https://practice.geeksforgeeks.org/problems/nth-node-from-end-of-linked-list/1
solution 1:
Time complexity O(n);
space complexity O(1)

int getNthFromLast(node *head, int n) {
    node*fast=head;
    node *slow=head;
    for(int i=1; i<n;i++){
        if(fast==0) return -1;
        fast=fast->next;
    }
    while(fast->next!=0){
        fast=fast->next;
        slow=slow->next;
    }
    return slow->data;

  }

solution 2: using stack

Space complexity O(n)

Time complexity O(n)

int getNthFromLast(node *head, int n)
  {
   stack<int> s;
   node *cu = head;
   int count = 0;
   while (cu != 0) {
    s.push(cu->data);
    cu = cu->next;
    ++count;
   }
   if (count < n) {
    return -1;
   }
   while (n != 1) {
    s.pop();
    --n;
   }
   return s.top();
   
  }``
int getNthFromLast(node *head, int n) {
   node *fast = head;
   node *slow = head;
   // slow will end up locate in the middle. 
   //n will be either on the right or left of slow
   int count = 0;
   while (fast != 0&&fast->next!=0) {
    fast = fast->next->next;
    count = count + 2;
    slow = slow->next;
   }
   if (fast != 0) ++count;
   if (count < n) return -1;
   int mid = (count + 1) / 2;
   if (n == mid) return slow->data;
   if (count == n) return head->data;
   if (n < mid) {// the node located to the right of n
    for (int i = 0; i < mid - n;i++) {
     slow = slow->next;
    }
    return slow->data;
   }
   else {
    slow = head;
    for (int i = 0; i < count - n; i++) {
     slow = slow->next;
    }
    return slow->data;
   }