Given a singly linked list, determine if it is a palindrome.
Example 1:
Input: 1->2
Output: false
Example 2:
Input: 1->2->2->1
Output: true
Follow up:
Could you do it in O(n) time and O(1) space?
My code:
# 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
"""
tail=head
prev=None
while tail:
tail.prev=prev
prev=tail
tail=tail.next
tail=prev
#then come two side
while head!=tail:
#print('head val %d, tail val %d'%(head.val,tail.val))
if head.val!=tail.val:
return False
if head.prev==tail.next and head.prev!=None:
return True
head=head.next
tail=tail.prev
#print('head val %d, tail val %d'%(head.val,tail.val))
return True
Solution: https://leetcode.com/problems/palindrome-linked-list/submissions/