O(n) - O(1) solution by reversing the second half (Python)


  • 2
    B
    class Solution(object):
        def isPalindrome(self, head):
            dummy = first = second = ListNode(None)
            dummy.next = head
            while second and second.next:
                first, second = first.next, second.next.next
            
            first.next, second = None, first.next
            while second:
                second.next, first.next, second = first.next, second, second.next
            
            second, first = first.next, dummy.next
            while first and second:
                if first.val != second.val: return False
                first, second = first.next, second.next
            return True

Log in to reply
 

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