**QUESTION**:

**Return Kth to Last**: Implement an algorithm to find the Kth to last element of a singly linked list.

**SOLUTION:**

- We will approach this problem both recursively and non-recursively.
- Remember that recursive solutions are often cleaner but less optimal.
**For example**, in this problem, the recursive implementation is about half the length of the iterative solution but also takes 0(n) space, where n is the number of elements in the linked list.

Note that for this solution, we have defined k such that passing in k=1 would return the last element, k=2 would return to the second to last element, and so on. It is equally acceptable to define k such that k = 0 would return the last element.

**Solution #1: If linked list size is known**If the size of the linked list is known, then the kth to last element is the (length – k)th element. We can

just iterate through the linked list to find this element. Because this solution is so trivial, we can almost be sure that this is not what the interviewer intended.

**Solution #2: Recursive**

- This algorithm recurses through the linked list.
- When it hits the end, the method passes back a counter set to 0.
- Each parent call adds 1 to this counter. When the counter equals k, we know we have reached the kth to the last element of the linked list

Implementing this is short and sweet-provided we have a way of”passing back” an integer value through

the stack. Unfortunately, we can’t pass back a node and a counter using normal return statements. So how do we handle this?

**Approach A: Don’t Return the Element.**

- One way to do this is to change the problem to simply printing the kth to the last element.
- Then, we can pass back the value of the counter simply through return values.

int printKthToLast(LinkedlistNode head, int k) { if (head== null) { return 0; } int index = printKthToLast(head.next, k) + 1; if (index == k) { System.out.println(k + "th to last node is "+ head.data); } return index; }

Of course, this is only a valid solution if the interviewer says it is valid.

**Approach B: Use C ++.**

- A second way to solve this is to use C++ and to pass values by reference.
- This allows us to return the node value, but also update the counter by passing a pointer to it.

node* nthToLast(node* head, int k, int& i) { if (head== NULL) { return NULL; } node* nd = nthToLast(head->next, k, i); i = i + 1; if (i == k) { return head; } return nd; } node* nthToLast(node* head, int k) { int i = 0; return nthToLast(head, k, i); }

**Approach C: Create a Wrapper Class.**

- We described earlier that the issue was that we couldn’t simultaneously return a counter and an index.
- If we wrap the counter value with a simple class (or even a single element array), we can mimic passing by reference

class Index { public int value } LinkedListNode kthTolast(LinkedlistNode head, int k) { Index idx = new Index(); return kthToLast(head, k, idx); } LinkedListNode kthToLast(LinkedListNode head, int k, Index idx) { if (head== null) { return null; } LinkedListNode node kthToLast(head.next, k, idx); idx.value = idx.value + 1; if (idx.value == k) { return head; } return node; }

- Each of these recursive solutions takes 0( n) space due to the recursive calls.
- There are a number of other solutions that we haven’t addressed. We could store the counter in a static variable. Or, we could create a class that stores both the node and the counter, and return an instance of that class. Regardless of which solution we pick, we need a way to update both the node and the counter in a way that all levels of the recursive stack will see.

**Solution #3: Iterative**

- A more optimal, but less straightforward, the solution is to implement this iteratively.
- We can use two pointers, p1 and p2.
- We place them k nodes apart in the linked list by putting p2 at the beginning and moving p1 k nodes into the list.
- Then, when we move them at the same pace, p1 will hit the end of the linked list after LENGTH – k steps. At that point, p2 will be LENGTH – k nodes into the list, or k nodes from the end.

**The code below implements this algorithm.**

LinkedListNode nthTolast(LinkedListNode head, int k) { LinkedlistNode pl head; LinkedlistNode p2 = head; /* Move pl k nodes into the list.*/ for (int i= 0; i < k; i++) { if (pl == null) return null; // Out of bounds pl = pl.next; } /* Move them at the same pace. When pl hits the end, p2 will be at the right * element. */ while (pl!= null) { pl pl.next; p2 = p2.next; } return p2; }

This algorithm takes O(n) time and 0(1) space.