Two methods for finding the NTH element from the reciprocal of a linked list

Method 1: use two Pointers p,q , first move q to the end of the list by n bits, and then move p and q back together. Then, when q reaches the end of the list, p points to the reciprocal NTH node of the list.

node* find_nth_to_last(node* head,int n) { if(head==NULL || n<1) return NULL; node*p,*q; p=q=head; while(q!=NULL && n--){ q=q->next; } if(n>=0) return NULL; while(p!=NULL && q!=NULL){ p=p->next; q=q->next; } return p; }

Method 2: the number of nodes can be calculated first , that is, the number m is obtained by traversing the linked list from beginning to end, so the reciprocal of the NTH element is also the m-n+1 element.
JAVA code:

LinkedListNode nthToLast(LinkedListNode head, int n) { if (head == null || n < 1) { return null; } LinkedListNode p1 = head; LinkedListNode p2 = head; for (int j = 0; j < n - 1; ++j) { // skip n-1 steps ahead if (p2 == null) { return null; // not found since list size < n } p2 = p2.next; } while (p2.next != null) { p1 = p1.next; p2 = p2.next; } return p1; }