Write an algortithm to find the $$n^{th}$$ node from the last node of a singly Linked list.
 Posted: 5 years ago Updated: 5 years ago 0 0 Edit Take two pointers $$pointer1$$ and $$pointer2$$ pointing at the head of the Linked List. Increment $$pointer2$$ by ($$n-1$$) locations such that the distance between $$pointer1$$ and $$pointer2$$ becomes $$n$$, $$i.e$$, $$pointer2$$ now points $$n^{th}$$ node. Increment $$pointer1$$ and $$pointer2$$ by $$1$$ until $$pointer2$$ reaches the last node of the list. $$pointer1$$ now points to the $$n^{th}$$ node from the last node of the list. Time complexity = $$O(n)$$.LinkedListNode findNthNodeFromEnd(LinkedListNode head, int n){ /* Empty linked list */ if (head == null || n < 1) return null; /* Initialize two pointers at the beginning of the list */ LinkedListNode pointer1 = head; LinkedListNode pointer2 = head; /* Increment pointer2 by (n-1) locations */ for (int j = 0; j < n - 1; ++j){ /* When the length of the list is less than n */ if (pointer2 == null) return null; /* Increment 1 location */ pointer2 = pointer2.next; } /* Increment both the pointers until pointer2 reaches the last node */ while (pointer2.next != null){ pointer1 = pointer1.next; pointer2 = pointer2.next; } /* pointer1 is now the nth node from the end - return it */ return pointer1; }