trjhtr

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()

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