Palindrome

Implement a function to check if a linked list is a palindrome.

Solution

To solve this problem, we can reverse the linked list and compare the result against the original linked list. Let’s write a function to reverse a linked list. The function will accept the head of the linked list, and return the head of the reversed linked list.

def reverse_list(node):
  head = None

  while(node != None):
    new = Node(node.value)
    new.next = head
    head = new
    node = node.next

  return head

Now, we need a function to compare two linked lists and validate that they are equal. This function will iterate through the lists simultaneously and return False if the values are ever different.

def is_equal(one, two):
  while(one != None and two != None):
    if(one.value != two.value):
      return False

    one = one.next
    two = two.next

  return True

Notice that the function above will not work if the lists are of different size. The while loop will terminate prematurely, and the function will return True if all of the values in the shorter list are equal to the values in the larger list. This is incorrect - lists of different sizes are not equal and the function should return False. However, since we are generating the second linked list, we can ensure that it is the same size as the parent.

The reverse_list function takes time \(O(n)\), and the is_equal function also takes time \(O(n)\). The total time of this algorithm is \(O(2n)\).