Data Structures and Algorithms in Python/

...

/

Is Palindrome

Is Palindrome

In this lesson, we'll learn how to determine whether a singly linked list is a palindrome or not.

We'll cover the following...

In this lesson, we investigate how to determine if a singly linked list is a palindrome, that is if the data held at each of the nodes in the linked list can be read forward from the head or backward from the tail to generate the same content. We will code the solution to both of these approaches in Python.

First of all, let’s learn what a palindrome is. A palindrome is a word or a sequence that is the same from the front as from the back. For instance, racecar and radar are palindromes. Examples of non-palindromes are ABC, hello, and test.

For this lesson, we’ll solve the Is Palindrome problem in Python by using three solutions.

Now let’s go ahead and check out Solution 1:

Solution 1: Using a string #

Implementation #

Press + to interact
def is_palindrome(self):
  # Solution 1:
  s = ""
  p = self.head 
  while p:
    s += p.data
    p = p.next
  return s == s[::-1]

Explanation #

The first solution makes use of a string, s, which is initialized to an empty string on line 3. Then we initialize p to self.head on line 4. On line 5, a while loop is set which will run until p becomes None. In the while loop, the data of the current node is concatenated to the string s on line 6 while we keep updating p to its next node on line 7. Finally, we return a boolean value based on the following condition on line 8:

s == s[::-1]

The condition above checks if s is equivalent to ...