CareerCup

public void findNthNode(int n){
		TNode curr=head;
		TNode temp=head;
		for(int i =0;i<n;i++){
			temp = temp.next;
		}
		while(temp!=null){
			curr = curr.next;
			temp = temp.next;
		}
		System.out.println("..... "+curr.val);
		
	}

The idea is to use two pointers that are of distance n.
Initially, advance the first pointer until the distance becomes n. Then advance both pointers simultaneously until the one at the end reached the end of the list. The other pointer will point to the required node.

Base: Create two pointers p1 and p2. Move p2 N nodes forward. ( handle situation if there are less than N nodes in list)
Step: each time save p2 into pointer p3 and try to move p2 N nodes forward.
If success, set p1 = p3 and repeat step.
If not - we moved p2 k times (k<N) and reached the end, so move p1 k times forward. node(p1) will be the answer because before this step there were N nodes between p1 and p2.

Below is the pseudo code (language agnostic)

itr = first_node;

for (i=0; i<N;i++) {
     itr = itr->next;
}
 itr_2 = first_node;
 while (itr->next != NULL) {
     itr = itr->next;
     itr_2 = itr_2->next;
 }
 println (itr_2.val);

The above solutions are wrong, they are not solving the problem of finding the nth element from last.
1) Calculate the length of Linked List. Let the length be len.
2) Print the (len – n + 1)th node from the begining of the Linked List.

/* Function to get the nth node from the last of a linked list*/
void printNthFromLast(struct node* head, int n)
{
    int len = 0, i;
    struct node *temp = head;
 
    // 1) count the number of nodes in Linked List
    while (temp != NULL)
    {
        temp = temp->next;
        len++;
    }
 
    // check if value of n is not more than length of the linked list
    if (len < n)
      return;
 
    temp = head;
 
    // 2) get the (n-len+1)th node from the begining
    for (i = 1; i < len-n+1; i++)
       temp = temp->next;
 
    printf ("%d", temp->data);
 
    return;
}

Recursive solution, python. since n can be of any value, you wanna also check for non positive integer.

For each node, this function returns a 3-tuple. (outcome_value, node_count_from_the_end, whether_the_job_is_done.)

So if the call to next node returns done, then the value is done and we return the result.
Otherwise, check to see if this node is the node we want by checking the node count from the end. increment count if not done.

#nth from last node of linkedlist

class Node(object):
    def __init__(self, data, next):
        self.data = data
        self.next = next

def nth_from_last(head, n):
    (value, count, done ) = nth_from_last_aux(head, n)
    if not done:
        return None
    else:
        return value
    
def nth_from_last_aux(head, n):
    if not head:
        return None
    if not head.next: #last node
        if n == 1:
            return (head.data, None, True)
        else:
            return (None, 1, False)
        
    (value, count, done) = nth_from_last(head.next, n)
    if done: 
        return (value, count, True)
    elif count+1 == n:
        return (head.data, count, True)
    else:
        return (value, count+1, False)
        
#test
h = Node(1, Node(2, Node(3, Node(4, None))))
print nth_from_last(h, 2)