This notebook was prepared by Donne Martin. Source and license info is on GitHub.

Solution Notebook¶

Constraints¶

• Can we assume this is a non-circular, singly linked list?
• Yes
• Is a single character or number a palindrome?
• No
• Can we assume we already have a linked list class that can be used for this problem?
• Yes
• Can we use additional data structures?
• Yes
• Can we assume this fits in memory?
• Yes

Test Cases¶

• Empty list -> False
• Single element list -> False
• Two or more element list, not a palindrome -> False
• General case: Palindrome with even length -> True
• General case: Palindrome with odd length -> True

Algorithm¶

• Iterate through the current linked list
• Insert to front the current node into a new linked list
• Compare the reversed list with the original list
• Only need to compare the first half

Complexity:

• Time: O(n)
• Space: O(n)

Note:

• We could also do this iteratively, using a stack to effectively reverse the first half of the string.

Code¶

In [1]:
%run ../linked_list/linked_list.py

In [2]:
from __future__ import division

def is_palindrome(self):
return False
length = 0

while curr is not None:
reversed_list.insert_to_front(curr.data)
length += 1
curr = curr.next

# Compare the reversed list with the original list
# Only need to compare the first half
iterations = length // 2
for _ in range(iterations):
if curr.data != curr_reversed.data:
return False
curr = curr.next
curr_reversed = curr_reversed.next
return True


Unit Test¶

In [3]:
%%writefile test_palindrome.py
import unittest

class TestPalindrome(unittest.TestCase):

def test_palindrome(self):
print('Test: Empty list')

print('Test: Single element list')

print('Test: Two element list, not a palindrome')

print('Test: General case: Palindrome with even length')

print('Test: General case: Palindrome with odd length')

print('Success: test_palindrome')

def main():
test = TestPalindrome()
test.test_palindrome()

if __name__ == '__main__':
main()

Overwriting test_palindrome.py

In [4]:
%run -i test_palindrome.py

Test: Empty list
Test: Single element list
Test: Two element list, not a palindrome
Test: General case: Palindrome with even length
Test: General case: Palindrome with odd length
Success: test_palindrome