Hi I am trying to solve the palindrome linked list problem from leetcode. I have produced a solution but I am unsure why it is incorrect. It would be really appreciated with someone can explain my misconception to me.

Question: Given the head of a singly linked list, return true if it is a palindrome or false otherwise. Full description can be found at https://leetcode.com/problems/palindrome-linked-list/

Here is my incorrect attempt (which looks sort of similar to the real solution)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    # returns bool true or false
    def isPalindrome(self, head):

        # reverse the linked list
        # define another same head for the reversion 
        reversedhead = head
        # Define a previous to invert the link
        prev = None
        # while head is not None
        while reversedhead:
            # temp variable
            current = reversedhead
            reversedhead = reversedhead.next
            current.next = prev
            prev = current

        while head:
            if prev.val != head.val:
                return False
            prev = prev.next
            head = head.next

        return True

Here is a solution that I found online:

class Solution:
    # returns bool true or false
    def isPalindrome(self, head):
        slow = head
        # find the mid node
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        # reverse the second half
        node = None
        while slow:
            nxt = slow.next
            slow.next = node
            node = slow
            slow = nxt
        # compare the first and second half nodes
        while node: # while node and head:
            if node.val != head.val:
                return False
            node = node.next
            head = head.next
        return True

My code looks sort of similar but it is wrong. The order of my statements inside the while loop is different that the order of the statements in the right solution. For the head [1, 1, 2, 1], my solution failed the test. My output was true but the expected output is false.

I think I have issues with understanding the head and node concept? The head is just the first node of the linked list right? In this case the first node/head would be 1?

I tried to debug on my own before asking, but pycharm is returning an error which I don't understand. How do I use [1, 1, 2, 1] as input to my solution?

q = Solution()
print(q.isPalindrome(ListNode(1, 1)))

reversedhead = reversedhead.next
AttributeError: 'int' object has no attribute 'next'

CodePudding user response：

Your idea seems to be the following:

1. reverse the list
2. walk forward along the list and at the same time walk backwards by the reversed list
3. If each compared value is the same, then it is a palindrome

The logical error is in step 2: you cannot walk forward anymore through the list, because it has been reversed. There is only one list. head is now the tail of that list, and thus head.next is None. So this loop will get into trouble in its second iteration, as at that point head is None.

The second, correct, algorithm, only reverses the second half of the list, so now there is a first half that can be traversed in forward manner, and a second half that can be traversed in backward manner. That way it will indeed work.

Alternatively, your idea would work if you would clone all nodes without mutating the original linked list nodes, and would reverse link those. Obviously that will allocate O(n) of memory, and is therefore less optimal than the correct solution you already quoted:

    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        reversedhead = None
        current = head
        while current:
            reversedhead = ListNode(current.val, reversedhead)
            current = current.next

        while head:
            if reversedhead.val != head.val:
                return False
            reversedhead = reversedhead.next
            head = head.next

        return True

As to testing this in a local environment: you should not pass a list to your function, but an instance of ListNode. While LeetCode does this for you before calling your function, in a local environment you'll have to prepare the input yourself.

Check out my answer on AttributeError: 'list' object has no attribute 'val' in linked list LeetCode challenge for how you can do that.