Given a singly linked list, determine if it is a palindrome.
Input: 1->2 Output: false
Input: 1->2->2->1 Output: true
Could you do it in O(n) time and O(1) space?
A palindrome, and its reverse, are identical to each other.
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def isPalindrome(self, head: ListNode) -> bool: reversed_head = self.reverse(head) while (head != None and reversed_head != None): if (head.val != reversed_head.val): return False head = head.next reversed_head = reversed_head.next return True def reverse(self, head): prev = None dummy = ListNode(0) dummy.next = head current = head while (current != None): new = ListNode(current.val) new.next = prev prev = new current = current.next head = dummy.next return prev
- Time complexity: O(N).
- Space complexity: O(1).