LinkedLists 203: From Last

Welcome back to another (and most likely the final) week of my linked list series. If you are generally unfamiliar with linked lists or want to check out other posts in this series, definitely take a look at my previous articles on this topic!

Otherwise, let’s just get right into solving our final linked list problem (at least for now!).

Just another list gif

The Problem

The goal of the from last problem is given both a linked list and an integer n, return the element n spaces from the last node in the list. For example, if n = 0, then we should return the last element. If n = 1, we want to return the second last element. If n = 2, we should return the third to last element. Etc.

Now, there are a couple of caveats to this problem. First, we can assume that n will always be less than the length of the list. Second, for this solution we are not going to be using a “size” method to determine the length of this list. While it might be easy to come up with a simple solution using the length of the list, instead, we are going to once again revisit the “Tortoise and the Hare Algorithm” and see how we can implement it in the solution to this problem.

The solution: Phase One

The solution to the “from last” problem is going to have two phases. In phase one, we are going to work with our fast variable, however, our use of the fast variable in this problem will slightly differ from how we have used it previously.

Instead of advancing our fast variable by two nodes at a time as we did in our previous solutions, we are going to start by advancing our fast pointer by n nodes. So, if n is three, we are going to move our fast variable to three nodes into our list.

To do this, we can use a simple while loop:

function fromLast(list, n) {
   let fast = list.head
   while (n > 0) {
      fast = fast.next
      n--
   }
}

The Solution: Phase Two

Now that we’ve completed the first phase of our solution, we can move on to our second and final phase.

Much like our first phase, this phase is also quite simple, though again its use of the fast variable differs from our other implementations of “Tortoise and the Hare Algorithm”. For this solution, both fast and slow will move forward one node at a time. Really, it might make a bit more sense to call our fast variable “head start” for this solution, however for consistency’s sake, we will stick with our original terms.

Now, as fast and slow move forward, we will check to check to see when fast reaches the end of the list aka when fast.next is null. Since we previously gave fast a head start by n nodes, we know that our slow variable will be n nodes behind our fast variable. Thus, when fast reaches the end of the list, our slow variable will be pointing to the node we are looking for and we can return the slow variable.

The Solution: Completed

function fromLast(list, n) {   
   let slow = list.head
   let fast = list.head
   while (n > 0) {
      fast = fast.next
      n--
   }
   
   while (fast.next) {
      slow = slow.next
      fast = fast.next
   }   return slow
}

There you have it! That’s our complete solution to our “from last” problem. I hope you’ve enjoyed this little series on linked lists. Definitely give these problems a try on your own and as always, good luck and happy coding!

bunny ❤