CODEWITHSUNDEEP
pythonlinked-list
Haxet
Haxet

Reputation: 73

Why is the head getting affected when I call my reverse function vs the case at the bottom? I get the none error

Here's the code. The head and the dummy node in ispalindrome gets changed after I call the reverse function. Any reason why this happens? I have a case in the bottom of doing the same thing where head doesn't get changed. 

class ListNode(object):
    def __init__(self,x):
        self.val=x
        self.next=None
def reverse(head,l):
    prev=None
    while head:
        head.next,prev,head=prev,head,head.next
        l+=1
    return (prev,l)

def isPalindrome(head):
    dummy=head
    rev,l=reverse(head,0)
    print (rev.val,dummy.next.val)

a=ListNode(1)
a.next=ListNode(2)

isPalindrome(a)

I did something similar here to test out my logic and this is the way I imagined my code to turn out: When I call reverse, I can still access the head and the b variable assigned to it.

class ListNode(object):
    def __init__(self,x):
        self.val=x
        self.next=None
a=ListNode(1)
a.next=ListNode(2)
b=a
def reverse(head,l):
    prev=None
    while head:
        head.next,prev,head=prev,head,head.next
        l+=1
    return (prev,l)
rev,l=reverse(a,0)
print b.val,rev.val

Upvotes: 0

Views: 89

Answers (2)

Blckknght
Blckknght

Reputation: 104722

The issue with your code is that your reverse function is destructive. That is, it creates a reversed list by modifying the list you pass to it. Afterwards, the original list doesn't exist in the same form any more.

This is problematic for a palindrome test, since you want to compare the list to its own reverse. If the original doesn't exist any more, the reversed version isn't very useful.

While there are various ways you could avoid your specific error, to solve the larger problem of getting a reversed list while still having a copy of the original, I think there is an easy fix. You can change the logic of reverse to create a copy of the list in reversed order, rather than modifying the original:

def reverse_copy(head, l):
    new_list = None
    while head:
        temp = Node(head.val)
        temp.next, new_list = new_list, temp
        l += 1
    return new_list, l

Now you can have isPalindrome do rev, l = reverse_copy(head), and still have head refer to the original list!

Upvotes: 1

niemmi
niemmi

Reputation: 17263

In the first version you store the original head to dummy and then reverse the list. This of course causes dummy to be the last node in the reversed list. Then you try to access value of next element from dummy: dummy.next.val This obviously fails because dummy.next is None.

On the second example you're not accessing the links at all, only the values. When you reverse the list you only change the links between the nodes but not the values so you can't detect the change.

Update To illustrate better on what's happening here I've added a new function that displays the list before and after reversal:

def to_str(head):
    l = []
    while head:
        l.append(str(head.val))
        l.append('->')
        head = head.next
    l.append('None')

    return ' '.join(l)

def isPalindrome(head):
    dummy=head
    print 'Before (dummy): {}'.format(to_str(dummy))
    rev,l=reverse(head,0)
    print 'After (dummy): {}'.format(to_str(dummy))
    print 'After (rev): {}'.format(to_str(rev))
    print (rev.val,dummy.next.val)

If you replace the original isPalindrome with above you get following output:

Before (dummy): 1 -> 2 -> None
After (dummy): 1 -> None
After (rev): 2 -> 1 -> None
Traceback (most recent call last):
  File "test.py", line 34, in <module>
    isPalindrome(a)
  File "test.py", line 29, in isPalindrome
    print (rev.val,dummy.next.val)
AttributeError: 'NoneType' object has no attribute 'val'

Upvotes: 1

Related Questions