O(n) time, o(1) space python solution


  • 1
    L

    1find the middle of the list

    2reverse the second half part

    3compare the first and the reversed second part

    class Solution(object):
    def getListLength(self, head):
        cnt = 0
        while head:
            head = head.next
            cnt += 1
        return cnt
    def inverseHalfList(self, head, n):
        # divide list into two parts, and inverse the second part
        pre_idx = (n - 1) / 2  # pre pointer
        pre = head
        for i in range(pre_idx):
            pre = pre.next
        # inverse the rest list
        # loop pre_idx-1 times
        p = pre.next
        for i in range(n - pre_idx - 2):
            tmp = pre.next
            pre.next = p.next
            p.next = p.next.next
            pre.next.next = tmp
        return pre_idx, pre.next
    
    def isPalindrome(self, head):
        n = self.getListLength(head)
        if n < 2:
            return True
        p = head
        j, q = self.inverseHalfList(head, n)
        # compare
        for t in range(n - j - 1):
            if p.val != q.val:
                return False
            p, q = p.next, q.next
        return True

  • 0
    D

    Is it possible to use O(1) space without modifying original data?


Log in to reply
 

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