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;
let head = null;
function Node(element) {
this.element = element;
this.next = null;
}
this.length = function() {
return length;
}
this.head = function() {
return head;
}
this.add = function(element) {
let node = new Node(element);
if (head == null) {
head = node;
} else {
currentNode = head;
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 currentNode = head;
let counter = 0;
while (counter < realTarget) {
currentNode = currentNode.next;
counter++;
}
return currentNode.element;
}
}
let congo = new LinkedList();
console.log(congo)
congo.add(5);
congo.add("Homeless");
congo.add("Real eyes realize real lies");
congo.length()
congo.head()
```

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();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
const head = list.head();
```

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`

Or a cyclic link

```
head.next = head; // now you have a infinit linked list
```

There function `LinkedList.add(data)`

will not exit.

## Don’t expose `node.next`

The solution is simple. Don’t expose the link. You can return items in the list wrapped in an object that provides a function next() to move to the next object. Or define the node with a getter for next.