Skip to content

Instantly share code, notes, and snippets.

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] =
return True
elif length == 0: # even
node[0] = head
return True
if not recurse(, length - 2, node):
return False # propagate Failure
if node[0].data !=
return False
node[0] = node[0].next
return True
def lengthOfList(ll):
count = 0
curr = ll.head
while curr:
count += 1
curr =
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.