LinkedList Palindrome

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s