Middle of the Linked List
I do it a-self! And in 20 minutes!
The Problem
Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
The Initial Attempts
Well, I solved it wrong the first time. Didn’t whiteboard, but the gist of it is, I created a hashmap (which I quickly realized could just be an array) to map the values in the list with where it fell in the list. Then I returned Math.floor of the length of the array divided by two. Easy peasy! But…wait. Wrong answer.
I realized then that it wanted me to return the last half of the linked list, from the center node on.
At that point I had a crying no-napping baby to deal with, so I went to get her and all the while my brain was working. How to find the center of a linked list without iterating through it more than once?
Of course. This is a classic Tortoise and Hare problem.
The Solution
Once I realized the kind of solution I was looking at, the code came pretty easily. I did have to consult a different linked list answer, because I’m not quite 100% on dealing with them without creating like, cyclic problems, but my issue was pretty easily correctable, and Leetcode accepted my solution shortly after my 20 minute timer went off. This, including the time it took to deal with Liesl and read her Peek-a-Who multiple times!
/**
* 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 middleNode = function(head) {
let pointerOne = head;
let pointerTwo = head;
while(pointerTwo && pointerTwo.next){
pointerOne = pointerOne.next;
pointerTwo = pointerTwo.next.next;
};
return pointerOne;
};Here’s what it does:
- First, I initialize some pointers, a slow one (pointerOne) and a fast one (pointerTwo).
- Next, while pointerTwo hasn’t reached the end and there’s still a pointerTwo.next:
- PointerOne moves to the next node
- PointerTwo moves two nodes over. This means, of course, that by the time there isn’t anymore pointerTwo or pointerTwo.next to be had, pointerOne will be at the center — since it’s moving at half the speed of pointerTwo!
- PointerOne is returned, and we move on with our day.
What I Learned
- Got another chance to recognize and work with the Tortoise and Hare algorithm. My big issue was that slowPointer was head.next, not slowPointer.next. So of course the thing was never going to complete and time out.
- Also got another chance to work with linked lists. Between linked lists and binary trees, I feel slightly better about linked lists. Not fully capable, but better.
Two more questions left in Week 2! One binary tree, ick, and one array, NBD. I’m really plugging away now.
mins
read
