Check if the Linked List is Palindrome or not

Question

When I try to check whether the linked list is palindrome or not, the following code gives me the error. My Approach is: Step 1:- I am reversing the linked list (temp = reverseLL(head). Step 2:- Checking elements of the reverse linked list to the original linked list. Step 3:- Returning True if it is palindrome else False

But my code is not working for the input [1,1,2,1], it shows me the result is True.

class Node:
def __init__(self, data):
        self.data = data
        self.next = None

def reverseLL(head):
    if head is None or head.next is None:
        return head
    rest = reverseLL(head.next)
    head.next.next = head
    head.next = None
    return rest


def checkpalindrome(head):
    temp = reverseLL(head)
    while head != None and temp != None:
        if temp.data != head.data:
            return False
        temp = temp.next
        head = head.next
    return True

Answer 1

The problem is that when the list has been reversed, the head node has become the tail, and so the palindrome check will compare the reversed list with its own tail node (that has no next node).

Realise that the reversed list does not create a new list. It is the original list that has been reversed and so there is no more possibility to traverse the list in its original order.

A solution that does not need O(n) auxiliary space is to only reverse half of the list and then you can compare the two halves.

Here is how your code could be adapted to achieve that:

def checkpalindrome(head):
    return isPrefixLL(head, reverseLL(centerLL(head)))

def centerLL(head):  # Retrieve the middle node (or the first of second half)
    fast = slow = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

def isPrefixLL(a, b):  # This is the comparison code you already had
    while a and b:
        if a.data != b.data:
            return False
        a = a.next
        b = b.next
    return True

Your reverseLL code can remain unchanged, although it uses extra stack space. If you really want to avoid O(n) auxiliary space, you should make it iterative -- which will also run slightly faster:

def reverseLL(head):
    tail = None
    while head:
        head.next, tail, head = tail, head, head.next
    return tail