Python object equality comparison

Question

wondering if I can get some help on this. Suppose you are trying to determine if a linked list is palindromic using something like this:

 def isPalindrome(self, head: ListNode) -> bool:

        current, prev = head, None

        if not head:
            return False

        if not head.next:
            return True

        while current:
            nextnode = current.next
            current.next = prev
            prev = current
            current = nextnode
            print(current, prev)
            if current:
                if current == prev or current.next == prev:
                    return True
        return False

Where a ListNode is defined as:

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

The thought here is begin restructuring for a reverse list and check for node equality (or next node equality for an even number of nodes) at each step. Running this code on a sample LL that points 1 -> 2 -> 2 -> 1 returns false but if we check objects that are being compared:

ListNode{val: 2, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}} ListNode{val: 1, next: None}
ListNode{val: 2, next: ListNode{val: 1, next: None}} ListNode{val: 2, next: ListNode{val: 1, next: None}}
ListNode{val: 1, next: None} ListNode{val: 2, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}
None ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 2, next: ListNode{val: 1, next: None}}}}

You can see in the output from the print that there is a case where the nodes appear to return identically structured lists (line 2). I assume that the comparison is failing because the starting point of either of the split lists, although a 2 -> 1, is a different 2 -> 1 in memory and thus the comparison fails?

If my understanding of why this fails is correct, is there a way to compare the nodes to make this work (without going outside of O(n) runtime)?

P.S. I don't want a different solution, I was just curious if there is a way to make this work :)

You should compare `current.val` to `prev.val` rather than the whole objects, unless you defined `__eq__` method in the `ListNode` class. — Błotosmętek, May 03 '20 at 22:04
Will clarify ListNode class in question, my mistake. I don't think that would in every case as if the same value node appears twice in the list such as 1 -> 3 -> 4 -> 1 -> 2, it would identify it as palindromic since the values are equal. — thekid77777, May 03 '20 at 22:07
This is a common general topic; I tried to find the most relevant answer I could as a "duplicate". The short version is that to compare your objects for value equality, you need to implement it. — Karl Knechtel, May 03 '20 at 22:11
If no `__eq__` method is defined for a class, objects of this class are considered equal only if they are the same object (ie. `a == b` if and only if `a is b`). See also https://stackoverflow.com/questions/1227121/compare-object-instances-for-equality-by-their-attributes — Błotosmętek, May 03 '20 at 22:15
I figured that was the case, hence the - I assume that the comparison is failing because the starting point of either of the split lists, although a 2 -> 1, is a different 2 -> 1 in memory and thus the comparison fails? If my understanding of why this fails is correct, is there a way to compare the nodes to make this work (without going outside of O(n) runtime)? — thekid77777, May 03 '20 at 22:16

Python object equality comparison

0 Answers0