# 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.)

``````function LinkedList() {
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

``````const list = new LinkedList();
``````

Delete second item from the list

``````head.next = head.next.next;
``````

Now the `length` you store is incorrect and the result of `findLast` will either return `index - 1`, `index + 1`, or worse throw if you reach the end as you will have assigned `null` to `currentNode` in the previous step and `currentNode.next` will throw `Can not read property "next" of null`

``````head.next = head; // now you have a infinit linked list
There function `LinkedList.add(data)` will not exit.