Today, we celebrate!
Tags: algorithms, computerscience
Published: 2020-05-03 19:49:44

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." 

![](https://media.giphy.com/media/l46CyJmS9KUbokzsI/giphy.gif)

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](https://leetcode.com/problems/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:

{% youtube kPU2ytDe92Q %}
   
And it seemed simple enough to code up so I did:

```javascript
/**
 * 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:

```javascript
...
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
    if (head === null) {
        return head;
    }
    let walker = head;
...
``` 

```javascript
    ...
    // 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: 
![Algorithm Relative performance. Faster than 88% of submissions. Uses less memory than 100% of submissions](https://dev-to-uploads.s3.amazonaws.com/i/ll5qt6zc5i2c4s0fw45t.png)