Ruby O(n) time and O(1) space solution with half-reversed list


  • 0
    S
    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
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.