Marc Lester Tan

My first solution for this easy LC problem involves traversing the whole linked list to find the total length. Then calculate the mid point and then use this to traverse the linked list again starting from root until mid point.

class Solution {
    fun middleNode(head: ListNode?): ListNode? {
        fun getLen(node: ListNode?) : Int {
            var n = node
            var ctr = 0
            while(n != null){
                n = n.next
                ctr++
            }
            
            return ctr
        }
        
        val len = getLen(head)
        var mid = len / 2
        
        var output: ListNode? = head
        (1..mid).forEach{
            output = output?.next
        }
        
        return output        
    }
}

Runtime: 140 ms, faster than 13.79% of Kotlin online submissions for Middle of the Linked List.
Memory Usage: 31.6 MB, less than 100.00% of Kotlin online submissions for Middle of the Linked List.

I honestly didn’t like the solution as it’s too verbose and it requires you to access some elements twice.

Here’s another approach but this time, we’re using a very common pattern of traversing linked list: Two-pointer approach. One pointer is a slow pointer which increments one node at a time and another pointer is the fast pointer which increments two nodes at a time.

When the fast pointer reaches the end, based on the requirements, we can either return the slow pointer as the output or it’s next node.

class Solution {
    fun middleNode(head: ListNode?): ListNode? {
        if(head?.next == null) return head
        
        var fastPtr: ListNode? = head.next.next
        var slowPtr: ListNode? = head
        
        while(true){
            slowPtr = slowPtr?.next
            if(fastPtr?.next == null) {
                break
            }else if(fastPtr?.next?.next == null){
                slowPtr = slowPtr?.next
                break
            }else fastPtr = fastPtr?.next?.next
        }
        
        return slowPtr       
    }
}

Runtime: 128 ms, faster than 68.97% of Kotlin online submissions for Middle of the Linked List.
Memory Usage: 31.4 MB, less than 100.00% of Kotlin online submissions for Middle of the Linked List.