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

Solution Notebook

Problem: Determine if a linked list is a palindrome.

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

  • Reverse the linked list
    • 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


class MyLinkedList(LinkedList):

    def is_palindrome(self):
        if self.head is None or self.head.next is None:
            return False
        curr = self.head
        reversed_list = MyLinkedList()
        length = 0

        # Reverse the linked list
        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
        curr = self.head
        curr_reversed = reversed_list.head
        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')
        linked_list = MyLinkedList()
        self.assertEqual(linked_list.is_palindrome(), False)

        print('Test: Single element list')
        head = Node(1)
        linked_list = MyLinkedList(head)
        self.assertEqual(linked_list.is_palindrome(), False)

        print('Test: Two element list, not a palindrome')
        linked_list.append(2)
        self.assertEqual(linked_list.is_palindrome(), False)

        print('Test: General case: Palindrome with even length')
        head = Node('a')
        linked_list = MyLinkedList(head)
        linked_list.append('b')
        linked_list.append('b')
        linked_list.append('a')
        self.assertEqual(linked_list.is_palindrome(), True)

        print('Test: General case: Palindrome with odd length')
        head = Node(1)
        linked_list = MyLinkedList(head)
        linked_list.append(2)
        linked_list.append(3)
        linked_list.append(2)
        linked_list.append(1)
        self.assertEqual(linked_list.is_palindrome(), True)

        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