find_nth_node_from_end_of_list.cpp

/*
struct ListNode {
    int val;
    ListNode* next;
};
 */

/**
 * return the nth node from the end of the list 
 * in O(N) time, O(1) space
 */
ListNode* getCorrespondingNode(ListNode* head, int n) {
    ListNode* a = head;
    ListNode* b = head;
    
    // make with first pointer n steps
    for (int i = 0; i < n; i++) {
        if (a != NULL) {
            a = a->next;
        }
    }
    
    /**
     * after that, continue with the same speed with both pointers
     * and when the first pointer reaches the end of the list, 
     * then the second pointer represents the Nth node 
     * from the end of the list
     */
    while (a != NULL && b != NULL) {
        a = a->next;
        b = b->next;
    }
    
    return b;
}