def length(p) c = 0 c, p = c + 1, p.next while p c end def is_palindrome(head) c = length(head) m = (c-1) / 2 current, pre = head, nil (m+1).times do current.next, pre, current = pre, current, current.next end reverse = c.odd? ? pre.next : pre while reverse && current return false if reverse.val != current.val reverse, current = reverse.next, current.next end true end
Ruby O(n) time and O(1) space solution with half-reversed list
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.