Algorithm Practice with Linked Lists
Finding the kth to the last node in a linked list
I’ve been solving challenges on Codewars most days lately, and today I thought I’d take a stab at an algorithm from Interview Cake (I signed up for their free 7-day email course to get a feel for it). Here’s what the problem required:
Write a method kth_to_last_node() that takes an integer k and the head_node of a singly-linked list, and returns the kth to last node in the list.
I read the prompt a couple of times and felt overwhelmed by questions like “How will I go backwards in a singly-linked list?!” and “How will I know where the end of the list is?!” before settling down and thinking through an approach to the problem. (If it wasn’t clear, I struggle sometimes at first glance with the abstract nature of algorithms — I have since I was first exposed to them in college — and this was no exception.)
Because the Firehose Project exposed me both to linked lists and to algorithmic problem solving, I felt like I could do it, yet it was still VERY tempting to look up solutions, write out the code that I found, test to make sure it worked, then read through the code to understand it later.
To challenge myself and help my brain move away from that approach, I googled around for some high level approaches to the problem, then tried my hand at writing the code to make the approach into an actual method.
The approach I landed on was to set two pointers k nodes apart in the list, then move them until the right-hand pointer reached the end of the list. At that point, the left-hand pointer would be k nodes from the end, solving the problem.
The Aha! Moment
Thinking about the problem in concrete, strategic terms with pointers helped make this problem feel way less daunting. I imagined putting two fingers an octave (or 8 white keys) apart on the A key of a piano keyboard, then moving them both along (still an octave apart) to B, C, D, E, F, G, A, etc… until I my right finger reached the high C on the keyboard. (This makes sense to my musically inclined brain. It may not be the best analogy for everyone, though.)
It was refreshing to notice how simple it felt to write the Ruby code for the kth_to_last_node() method once I had a high-level approach and a visualization to help me out.
Here’s the solution I came up with— lines 10–24 specifically are mine:
This was great practice for me, and I think the approach I took was a good way to scaffold (read: gradually move toward independence) solving algorithms. It proved to me that writing the code isn’t necessarily the blocker when I’m facing a tough problem; rather, it’s visualizing (what are to me) abstract concepts like linked lists and nodes and pointers, then finding a way to make them concrete. I’m going to try to this process when solving a few more algorithms, and then eventually stop looking for high level approaches altogether and instead rely on my own brain for that… We shall see how it goes!