CODEWITHSUNDEEP
pythonlinked-list
Dawn17
Dawn17

Reputation: 8297

Checking whether a linked list is palindrome. Cannot find the issue

class Solution(object):
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if head == None:
            return True

        if head.next == None:
            return True

        slow = head
        fast = head

        if fast.next.next == None:
            return fast.val == fast.next.val

        length = 1

        lenPtr = head

        while lenPtr.next != None:
            length += 1
            lenPtr = lenPtr.next

        while fast != None and fast.next != None:
            slow = slow.next
            fast = fast.next.next

        if length % 2 == 0: # even
            rev = self.reverse(slow)

        else:
            rev = self.reverse(slow.next)

        slow = None

        print(rev.val,  head.val, head.next.val)
        return rev == head

    def reverse(self, head):

        if head.next == None:
            print('return head', head.val)
            return head

        tempHead = head

        while head.next != None:
            temp = head.next
            head.next = head.next.next
            temp.next = tempHead
            tempHead = temp

        return tempHead

Here is my solution for a coding interview question that finds whether a linked list is a palindrome.

My strategy is just to find the midpoint of the linked list by using two pointers with different speed and reverse the second half of the list and then compare with the first half.

After I debugged, the problem is that the first half of the linked list does not remove the last node when it's an odd-length list. For example, if an input is 1->0->1->None, the second half will end up being 1->None and the first half should be 1->None too since I did slow = None after getting the reversed second half.

However, it seems like it still has the 0 node even after setting slow = None. This is very weird because head.next == slow returns true when I try to debug it.

What can possibly be the issue?

Upvotes: 1

Views: 204

Answers (1)

SHG
SHG

Reputation: 2616

Think about slow as a pointer to a node in the list. Setting it to None doesn't change the node it pointed to before, it just sets slow to point to another node, or to a None node in your case. So it doesn't point to 0 anymore, but 0 still exists and still in its place, pointed by head.

So head.next is still pointing to the next node which is 0 and therefore the first half of your list is 1->0->None.

Upvotes: 1

Related Questions