Most of the time when I am doing algorithmic practice problems, it takes a while for me to form the solution if I can even do it at all. Even for "easy" problems. If I do manage to solve it, I look at the solution(s) that other people post and think to myself: "I would not have thought of that, that quickly. And definitely not in an interview setting."
Today though, today was different. Today something special happened for the first time.
I read the "medium" level problem through once and within 5 seconds my brain came up with something that seemed like it could work and was optimal. The problem is called Rotate List on leetcode.com. Here is the problem's description
Given a linked list, rotate the list to the right by k places, where k is non-negative.
Example 1:
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
Example 2:
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL
Pause ⏸
Here is where I have to be somewhat responsible and tell you to try the problem out before before reading on. Not necessarily coding it up. Just see what your brain comes up with.
Play ▶️
Okay, welcome back.
Alright so I read the problem once and my inner voice immediately says to me, what if we made it a loop and just cut it in the new location? And I kid you not it came with a visual
Imagine me, imagining this:
And it seemed simple enough to code up so I did:
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var rotateRight = function(head, k) {
let walker = head;
let length = 0;
while(walker !== null) {
length++;
// Stop just before the end
if(walker.next === null) {
break;
}
walker = walker.next;
}
// Make the loop
walker.next = head;
// shifting the end forward 1 position is the same as shifting the end
// back (length - 1) positions
let newHeadPos = length - k;
let currentPos = 0;
walker = head;
// Stop just before the new head
while(currentPos < newHeadPos - 1) {
currentPos++;
walker = walker.next;
}
head = walker.next;
// Cut all ties https://media.giphy.com/media/ADSJHOoIvyjKM/giphy.gif
walker.next = null;
return head;
};
This was mostly correct. As with a lot of programming, edge cases will be the death of me. It failed when k > length and the linked list was empty. So I added an early return if the list was empty and modulo'd the k value to keep it in bounds.
The two adjustments:
...
* @return {ListNode}
*/
var rotateRight = function(head, k) {
if (head === null) {
return head;
}
let walker = head;
...
...
// shifting the end forward 1 position is the same as shifting the end
// back (length - 1) positions
let newHeadPos = length - (k % length);
...
But the programming is not the story here. The big thing, the HUGE thing, is that for the first time my brain came up with a solution to a problem I have never seen before almost immediately and it felt AMAZING.
Maybe there's a more optimal solution. I can kind find that out later. For this brief moment in time however, I was smarter than I gave myself credit for.
Today, we celebrate:
Top comments (0)