Skip to content

Instantly share code, notes, and snippets.

@bahriddin
Created November 19, 2018 11:59
Show Gist options
  • Save bahriddin/862c9a6cf754fb08ebdd934c0222d197 to your computer and use it in GitHub Desktop.
Save bahriddin/862c9a6cf754fb08ebdd934c0222d197 to your computer and use it in GitHub Desktop.
# 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
"""
if head is None:
return True
length = 0
node = head
while node:
node = node.next
length += 1
_, res = self.recIsPal(head, 0, length-1)
return res
def recIsPal(self, node, c1, c2):
"""
:type node: ListNode leftNode
:type c1: leftNode index
:type c2: rightNode index
:rtype: (rightNode, bool)
"""
# when list lenght is odd
if c2 == c1:
return node.next, True
# when list length is even
if c2 == c1 + 1:
return node.next.next, node.val == node.next.val
nodeLast, isPal = self.recIsPal(node.next, c1+1, c2-1)
return nodeLast.next, node.val == nodeLast.val and isPal
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment