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

by

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.

Leave a Comment