Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Determine if a LinkedList is a Palindrome Recursively
def isLinkedListPalindromeRecursive(ll):
'''
Recursively (recurse halfway (left), then pass down the next node (right) when recursing back through the stack)
This is the same as creating a stack in the first half and iterating through the next and popping
time: o(n)
space: o(n)
where n is the # of nodes in the list
'''
return recurse(ll.head, lengthOfList(ll), [None])
def recurse(head, length, node):
if length == 1: # odd
node[0] = head.next
return True
elif length == 0: # even
node[0] = head
return True
if not recurse(head.next, length - 2, node):
return False # propagate Failure
if node[0].data != head.data:
return False
node[0] = node[0].next
return True
def lengthOfList(ll):
count = 0
curr = ll.head
while curr:
count += 1
curr = curr.next
return count
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.