Palindrome Linked List

Условие

Дана голова односвязного списка, определите, является ли список палиндромом.

Примеры

Input: head = [1, 2, 2, 1]

Output: true

Input: head = [1, 2]

Output: false

Решение

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
fun isPalindrome(head: ListNode?): Boolean {
    if (head == null || head.next == null) return true // Если список пуст или содержит один элемент, это палиндром

    // Найдем середину списка с помощью двух указателей
    var slow = head
    var fast = head

    while (fast?.next != null) {
        slow = slow!!.next // Указатель медленный движется на один шаг
        fast = fast.next.next // Указатель быстрый движется на два шага
    }

    // Разворачиваем вторую половину списка
    var prev: ListNode? = null
    var current = slow
    while (current != null) {
        val next = current.next
        current.next = prev
        prev = current
        current = next
    }

    // Сравниваем первую и вторую половины
    var left = head
    var right = prev

    while (right != null) {
        if (left?.`val` != right.`val`) return false // Если значения не равны, это не палиндром
        left = left.next
        right = right.next
    }

    return true // Если все значения совпадают, это палиндром
}

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

O(n), где n — количество элементов в списке.

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

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