Условие

Дан односвязный список, в котором хранятся только 0 и 1. Каждый узел представляет собой один бит числа. Необходимо преобразовать двоичное число, представленное списком, в целое десятичное число.

Примеры

Input: head = [1, 0, 1] Output: 5 Explanation: (1 * 2²) + (0 * 2¹) + (1 * 2⁰) = 5

Input: head = [0] Output: 0

Решение

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
fun getDecimalValue(head: ListNode?): Int {
    var num = 0
    var current = head
    while (current != null) {
        num = num * 2 + current.`val` // Сдвигаем число влево и добавляем текущий бит
        current = current.next
    }
    return num
}

Временная сложность

O(n), где n — число узлов в списке.

Пространственная сложность

O(1), так как используется постоянное количество памяти.