The Problem

Here's another easy problem, which I'm grateful for.

This problem wants me to return the center node of a linked list.

My initial thought was I could traverse the list and push each one onto an array. Once I have the full array, I find the middle one and return it.

The code 

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function middleNode(head: ListNode | null): ListNode | null {
    let current = head;
    const visited = [head]
    while(current?.next){
        visited.push(current.next);
        current = current.next;
    }
    const fullLength = visited.length;

    if(fullLength % 2 === 0){
        return visited[fullLength/2]
    }
    return visited[(fullLength - 1) / 2]
};

According to Leetcode, this solution ran in 0ms and beat 100% of other solutions. I don't believe it.

Another solution

I looked it up, and apparently another way to do this that is better in terms of space complexity is to use our old friends two pointers and have a fast and a slow pointer. The fast pointer would move twice as fast, and therefore hit the end of the list when the slow pointer is at the middle. Let me try this out. 

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function middleNode(head: ListNode | null): ListNode | null {
    let fast = head;
    let slow = head;
    while(fast?.next){
        if(fast.next.next){
            fast = fast.next.next;
        }
        else{
            fast = fast.next
        }
        slow = slow?.next;
    }
    return slow;
};

Huh - this was even simpler. Cool.

Takeaways

I appreciate being at the point where easy problems are indeed easy. Also, a pattern to put in my back pocket is the concept of using node traversal at different speeds to find things.