Implement an algorithm to find the nth to last element of a singly linked list.

**My initial thoughts:**

Finding the nth to last element = Finding the (size – n + 1) first element. So we first get the size of the list and then traverse from the beginning.

**My initial codes:**

public static LLNode<Integer> nthLastElement(LLNode<Integer> head, int n) { int size = 0; LLNode<Integer> current = head; while (current != null) { size++; current = current.getNext(); } int pos = size - n + 1; int i = 1; if (pos == 1) return head; else current = head; do { i++; current = current.getNext(); } while (current != null && i != pos); return current; }

Comments after running:

- Works fine for most inputs. Time complexity O(n) and space complexity O(1).
- Failed for empty list. Add one sentence after highlighted line:
if(head == null || n < 0 || n > size) return null;

**Solution:**

The solution gives another insight of this question:

- Create two pointers, p1 and p2, that point to the beginning of the node.
- Increment p2 by n-1 positions, to make it point to the nth node from the beginning (to make the distance of n between p1 and p2).
- Check for p2->next == null if yes return value of p1, otherwise increment p1 and p2. If next of p2 is null it means p1 points to the nth node from the last as the distance between the two is n.
- Repeat Step 3.

public static LLNode<Integer> nthToLast(LLNode<Integer> head, int n) { if (head == null || n < 1) { return null; } LLNode<Integer> p1 = head; LLNode<Integer> 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.getNext(); } while (p2.getNext() != null) { p1 = p1.getNext(); p2 = p2.getNext(); } return p1; }Advertisements

Walt

Nov 12, 2012@ 18:28:14Awesome post!

This page also gives a good solution as well (and also the recursive solution):

http://www.programmerinterview.com/index.php/data-structures/find-nth-to-last-element-in-a-linked-list/