(Recursive + Iterative) Python Solution without Extra Space O(1)


  • 0
    U
    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
        def isPalindrome(self, head):
            """
            :type head: ListNode
            :rtype: bool
            """
            first = head
            second = head
            
            if not head or not head.next:
                return True
            
            number = 0
            while second and second.next:
                second = second.next.next
                number += 1
                if second:
                    first = first.next
            
            first.next = self.reverse(first.next)
            second = first.next
            first = head
            
            while number:
                if first.val != second.val:
                    return False
                first = first.next
                second = second.next
                number -= 1
            
            return True
            
    
        def reverse(self, head):
            if not head.next:
                return head
            
            new_head = self.reverse(head.next)
            head.next.next = head
            return new_head
    

Log in to reply
 

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