Check if a given linked list is palindrome

Question

I am solving interview questions from here.

Problem :Given a singly linked list, determine if its a palindrome. Return 1 or 0 denoting if its a palindrome or not, respectively.

Notes:Expected solution is linear in time and constant in space. For example, List 1-->2-->1 is a palindrome. List 1-->2-->3 is not a palindrome.

How can this solution be improved ?

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def __init__(self,seq):
        """prepends item of lists into linked list"""
        self.head = None
        for item in seq:
            node = ListNode(item)
            node.next = self.head
            self.head = node
              
    
    def list_palin(self):
        """ Returns 1 if linked list is palindrome else 0"""
        node = self.head
        fast = node
        prev = None
        ispal = True

        # prev approaches to middle of list till fast reaches end or None 
        while fast and fast.next: 
            fast = fast.next.next
            temp = node.next   #reverse elemets of first half of list
            node.next = prev
            prev = node
            node = temp

        if fast:  # in case of odd num elements
            tail = node.next
        else:    # in case of even num elements
            tail = node
      
        
        while prev and ispal:
            # compare reverse element and next half elements          
            if prev.val == tail.val:
                tail = tail.next
                prev = prev.next
                ispal = True
            else:
                ispal = False
                break
      
        if ispal :
            return 1
        else :
            return 0
# Test Cases
listpal_1 = Solution([7, 8, 6 ,  3 , 7 ,3 , 6, 8, 7])
assert listpal_1.list_palin()
listpal_2 = Solution([6 , 3 , 7, 3, 6])
assert listpal_2.list_palin()
listpal_3 = Solution([3, 7 ,3 ])
assert listpal_3.list_palin()
listpal_4 = Solution([1])
assert listpal_4.list_palin()

Answer 1

More tests

Having a test suite is nice. It would be even nicer to make it more comprehensive by adding:

• edge cases (empty list for instance)
• inputs with an even number of elements
• negative test cases : input is not a palindrome.

Here is a suggestion, I took this chance to remove the duplicated logic by extracting the data into a proper data structure:

# Test Cases
tests = [
    ([], True),
    ([1], True),
    ([1, 1], True),
    ([1, 2], False),
    ([3, 7, 3], True),
    ([3, 7, 4], False),
    ([6, 3, 7, 3, 6], True),
    ([7, 8, 6, 3, 7, 3, 6, 8, 7], True),
    ([7, 8, 6, 3, 7, 4, 6, 8, 7], False),
]
for inp, expected in tests:
    res = Solution(inp).list_palin()
    if res != expected:
        print("%s: %d != %d" % (inp, res, expected))

Using the boolean type

The bool type is expected for this type of situation (even if in Python, booleans are also integers equal to 0 or 1).

Many things can be simplified then:

    if ispal :
        return 1
    else :
        return 0

becomes:

    return ispal

Also, you can return False directly in the else block of the while loop. Then, it becomes more obvious that you never assign False to ispal. You can get rid of it and all the logic around it.

def list_palin(self):
    """ Check if linked list is palindrome and return True/False."""
    node = self.head
    fast = node
    prev = None

    # prev approaches to middle of list till fast reaches end or None 
    while fast and fast.next:
        fast = fast.next.next
        temp = node.next   #reverse elemets of first half of list
        node.next = prev
        prev = node
        node = temp

    if fast:  # in case of odd num elements
        tail = node.next
    else:    # in case of even num elements
        tail = node

    while prev:
        # compare reverse element and next half elements          
        if prev.val == tail.val:
            tail = tail.next
            prev = prev.next
        else:
            return False
    return True

Do we need that much code?

Depending on what you are trying to achieve personally, you may or may not need to re-implement a linked list.

Also, having a class named Solution seems a bit awkward here.

Function/method to compare list

The final block of the function compares 2 lists. It may be worth moving this to a function on its own.

Even better, you could define an __eq__ method in the ListNode class:

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

    def __eq__(self, other):
        return isinstance(other, ListNode) and self.val == other.val and self.next == other.next

and then just write:

    if fast:  # in case of odd num elements
        tail = node.next
    else:    # in case of even num elements
        tail = node

    return prev == tail