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

Posted on

Problem

I wrote this algorithm to find the Kth element of a singly linked list and I would like your feedback because I want to know if there is a better version.

In my eyes, this is the most optimized way of doing it and I’ve covered every edge case (I also assumed that the only possible input is a number, if I removed that assumption, I would add another if block), but I really would appreciate your feedback.

PS: I also only added these two main methods (add and findLast) because I figured that there were the only two required to find a solution, but I’m not sure if I should add more in an interview (i.e. remove, removeAt, addAt, isEmpty, etc.)

let length = 0;

function Node(element) {
this.element = element;
this.next = null;
}

this.length = function() {
return length;
}

}

let node = new Node(element);

} else {

while (currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = node;
}
length++;
}

this.findLast = function(index) {
if(index > length) {
return false;
}
if (index < 0) {
return false;
}

let realIndexes = length-1; // if length = 5, realIndexes = 4
let realPosition = index-1; // if index = 2, realPosition = 1
// We are looking for the real position here.
let realTarget = realIndexes - realPosition;
let counter = 0;

while (counter < realTarget) {
currentNode = currentNode.next;
counter++;
}
return currentNode.element;
}
}

console.log(congo)
congo.length()

Output: => 5

Solution

To get the sub-list of the last n elements without computing the length first (see comments):

• Go ahead with an end pointer until you have skipped n elements.
• Now go ahead in parallel with a start pointer and the end pointer until the end pointer reaches the end of the list (the start and end pointers will stay n elements apart as you go).
• Now start points to the desired sub-list.

In an interview, before you implement anything, it’s often a good idea to first describe your plan. Counting first works and is no different in terms of the O notation, but I doubt it’s what the interviewer wanted to see. Describing your plan can avoid spending time on something the interviewer might not really be interested in.

## Unsafe code

We can only guess what the interviewer is looking for. Usually they just want to know if you can write code in whatever language is required.

So the following is just to point out a danger in the code. Should you change your code? I can’t say..

## Protect state

Your function is flawed and can easily have its state corrupted. This is because you expose Node.next and don’t consider the various problems this will cause.
eg

Delete second item from the list