# Check if a given linked list is palindrome

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"""
for item in seq:
node = ListNode(item)

def list_palin(self):
""" Returns 1 if linked list is palindrome else 0"""
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()

• is the input just a list....do you need to convert it to a ListNode? – depperm Jun 6 '18 at 16:03
• @depperm the inputs are not provided by the site, only the function list_palin is open for writing the code, rest all is inbuilt in the site. I didn't find any better way to take inputs by self. – Latika Agarwal Jun 6 '18 at 16:33
• Is this linear in space? It seems to be building a reversed copy of the linked list. – Wayne Conrad Jun 6 '18 at 22:32

### 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."""
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

• Note that returning a bool fails to conform to the spec here. – Schism Jun 6 '18 at 20:45
• @Schism Yeah, well, not all interview questions are created equal, time for the old "I wuold have requested a boolean" to score bonus points in your interview. – Maarten Bodewes Jun 6 '18 at 23:13