leetcode day 16: linked list middle

Given a linked list, find the middle node. For an odd number of nodes, we want node [n/2]+1; for an even number, we want node [n/2].

The brute force method would run the length of the list, count up the number of nodes, and then start over from the beginning, counting off the appropriate number.

However, if we think about what the pointers do (one moves all the way, one moves halfway), we can do both at the same time, and use the “I ran off the end” condition to know when to check the pointer trying to get to halfway.

To do this, we run a fast pointer and a slow one, just like the loop detector tortoise and hare (and I’m patting myself on the back for having that insight), but in this case we use the fact that the lagging pointer moves exactly half as fast to ensure that it’s only gone halfway when the fast pointer runs off the end.

I had a little trouble getting the conditions right, but the final version that hits the right spots is this one:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    // tortoise and hare solution
    if head == nil {
        return nil
    }

    p := head
    q := head
    // we're not at the end, and there's at least one node past
    // this one, so q.Next.Next to jump forward 2 is valid.
    for q != nil && q.Next != nil {
        q = q.Next.Next
        // p moves forward one so that it will have moved half
        // as far. When q runs off the end, p will be at the halfway
        // point.
        p = p.Next
    }
    return p
}

This is clever in that it comes up with a nice way to combine the two actions, but not “clever” in the sense of “how does this even work”. This feels like a good strong choice rather than a “look how clever I am with character values” fragile one.