Grind 75 Question 19: Reverse Linked List
This feels familiar…
Before I dive into the problem, you may be asking, “What happened to questions 16-18?” (Okay, you probably aren’t, but let’s just pretend this blog has actual readers.) The questions are done, my friends. Yesterday was a big day — I frontloaded today so I would make sure to do my practice CodeSignal assessment (more on that later? maybe?) before the kids were in bed, since you can only take one 24 hours after the completion of the last one, it appears. My timing was off, so I wouldn’t have been able to start yesterday’s until like 9:30 pm, which is a half hour after my bedtime, man.
So, TL;DR: I did a bunch of extra Grind75 questions (ha, 3 1/2 is “a bunch”, I guess) so I could take today off, but here I am again. I finished my assessment at like 6:50 am, so I have the whole day ahead of me. Wahoo!
Maybe in the future I’ll post the Three Missing Questions. Or maybe I’ll leave ’em be. The first (Ransom Note) I got all by meself; the second (Climbing Stairs) I knew immediately was a classic recursion question but still needed Neetcode to explain it to me; the third (Longest Palindrome) I believe I got on my own, though I should still visit Neetcode, because I’m sure his solution is far more elegant.
That brings me to today’s first problem, Reverse Linked List.
The Problem
Given the head of a singly linked list, reverse the list, and return the reversed list.
The First Attempts
I swear to you, I’ve already done this problem. I know that I have to create a temporary variable to store something…I thought I could just sort of knock it out, but I spent way too long yesterday trying to reverse the damn list. Here’s what I have so far:
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
let reversedList = new ListNode();
while(head){
let reversedList.val = temp;
reversedList = reversedList.next;
reversedList = head.val
reversedList.next = temp;
}
return reversedList.next;
};I will spend ten more minutes trying to tweak it and then turn to Neetcode.
The Solution
Okay, well. I was close, but also not. Here’s the winning answer (iterative — I also watched the recursive explanation, but I’m still a little baffled by recursion):
var reverseList = function(head) {
let temp = null
while(head){
const next = head.next;
head.next = temp;
temp = head;
head = next
}
return temp;
};What it’s doing:
- We create a temporary variable and initialize it as null. That will be the end of the linked list (eventually).
- While head exists:
- We store head.next in the variable next
- We say place temp in the head.next spot
- We temporarily stash head in temp
- The new head becomes next (what was once head.next)
It’s a bit wacky, but I guess it works. I’m still bitter that I couldn’t figure it out on my own, but I suppose that just means I need to get more practice with linked lists.
What I Learned
- More manipulation of linked lists!
- I need more practice. Lots and lots and lots…
mins
read
