// MARK: - 234. Palindrome Linked List

//public class ListNode {
//    public var val: Int
//    public var next: ListNode?
//    public init() { self.val = 0; self.next = nil; }
//    public init(_ val: Int) { self.val = val; self.next = nil; }
//    public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
//}

func isPalindrome(_ head: ListNode?) -> Bool {

    // 1
    // Нужно найти середину связанного списка. Метод быстрого и медленного указателей
    // Медленный курсор будет идти на 1 шаг, Быстрый - на 2 шага
    // Когда быстрый курсор дойдет до конца списка, медленный дойдет до половины списка

    var slow = head
    var fast = head

    // этими условиями обрабатываем четность и нечетность линкед листа
    while fast != nil && fast?.next != nil {
        slow = slow?.next
        fast = fast?.next?.next
    }

    // теперь slow на середине

    //2
    // Нужно взять дальнюю половину и развернуть
    // Так, от головы элементы будут идти как и шли до центрального элемента
    // Указатель будет в самом конце обновленного списка и мы сможеи пройти к середине сравнивая элементы

    var prev: ListNode?
    while slow != nil {
        var temp = slow?.next
        slow?.next = prev
        prev = slow
        slow = temp
    }


    var left = head
    // в prev будет последний элемент
    var right = prev

    // Центральный элемент будет ссылаться на nil
    // Когда правый указатель упрется в nil, то это будет означать что мы прошли до середины списка
    while right != nil {
        if left?.val != right?.val {
            return false
        }
        left = left?.next
        right = right?.next
    }

    return true
}