Since it’s a singly linked list(no `prev`) we can’t use two pointers to check for palindrome in single pass.

We can however, if we break the list from the middle, reverse the second half and then compare each element of the two halves. But we must be careful with odd-even length.

We need following functionality:

1. Divide from the middle

1. Reverse half

2. Compare the two halves.

To get the middle element we can use the tortoise and hare approach.

def get_middle(head):
slow = head
fast = head
slow_prev = None
while fast != None and fast.next != None:
prev = slow
slow = slow.next
fast = fast.next.next
return slow,prev

This will return the middle element. In case of the odd list, the second half will get an extra element. We don’t have to worry about it, as on reversal it will get to the last. (We’ll make sure we don’t do anything with the last element if their are odd nodes).

Here is a simple reversal method that takes middle node.

def reverse(current_node):
prev = None
while current_node:
next_node = current_node.next
current_node.next = prev
prev = current_node
current_node = next_node
return prev

But we have to “break” the first half from the second half. Thats why our ` get_middle`

returned the prev node too, so we can ` prev.next = None`

.

Now we have two pointers to the head of each halves and compare one by one.

def get_middle(head):
slow = head
fast = head
slow_prev = None
while fast != None and fast.next != None:
prev = slow
slow = slow.next
fast = fast.next.next
return slow,prev
def reverse(current_node):
prev = None
while current_node:
next_node = current_node.next
current_node.next = prev
prev = current_node
current_node = next_node
return prev
def is_list_palin(head):
middle_node, middle_prev = get_middle(head)
new_middle_node = reverse(middle_node)
middle_prev.next = None
A = head
B = new_middle_node
while A and B:
if A.val != B.val:
return False
A = A.next
B = B.next
return True
import scratch_pad
print is_list_palin(scratch_pad.a)

### Like this:

Like Loading...