876.middle-of-the-linked-list.md

876. Middle of the Linked List

data class ListNode(
    val value: Int,
    var next: ListNode? = null
)

fun middleNode(head: ListNode?): ListNode? {
    val size = getSize(head)
    val middle = size / 2
    var i = 0
    var node = head
    while (i < middle) {
        node = node?.next
        i++
    }
    return node
}

private fun getSize(head: ListNode?): Int {
    var node = head
    var size = 0
    while (node != null) {
        size++
        node = node.next
    }
    return size
}

We also can achieve by two pointers approach, slow pointer goes 1 step, fast pointer goes 2 step, when fast pointer reaches the end, slow pointer is at the middle.

1 -> 2 -> 3 -> 4 -> _
          M
F         F         F
S    S    S

1 -> 2 -> 3 -> _
     M
F         F
S    S

fun middleNode(head: ListNode?): ListNode? {
    var slow: ListNode? = head
    var fast: ListNode? = head
    while (fast?.next != null) {
        slow = slow?.next
        fast = fast?.next?.next
    }
    return slow
}

Equivalence, but it's recommended to use above implementation, especially in problem 141. Linked List Cycle.

fun middleNode(head: ListNode?): ListNode? {
    var slow: ListNode? = head
    var fast: ListNode? = head?.next
    while (fast != null) {
        slow = slow?.next
        fast = fast?.next?.next
    }
    return slow
}