逆関数を呼び出すと、頭が下にあるケースと対立するのはなぜですか？私はnoneエラーを受け取ります

Question

ここにコードです。 ispalindromeの頭とダミーノードは、逆関数を呼び出した後に変更されます。これが起こる理由は何ですか？私は、頭が変わらない同じことをする最中に事件がある。

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) 

私は私のロジックをテストするためにここに似た何かをした、これは私が判明する私のコードを想像方法です：私は逆呼び出すと、私はまだ頭とそれに割り当てられたB変数にアクセスすることができます。あなたはdummy元の頭を格納し、リストを逆に最初のバージョンで

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 

Answer 1

コードの問題は、reverse機能が破壊的であることです。つまり、渡されたリストを変更して、逆のリストを作成します。その後も、元のリストは同じ形式では存在しません。

これは、リストを独自の逆に比較したいので、回文テストで問題になります。元のものがもう存在しない場合、逆のバージョンはそれほど有用ではありません。

特定のエラーを回避するにはさまざまな方法がありますが、元のコピーを残したまま逆引きリストを取得するという大きな問題を解決するには、簡単な修正があると思います。あなたは、むしろ元を変更するよりも、逆の順序でリストのコピーを作成するためにreverseのロジックを変更することができます。

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 

今、あなたはisPalindromeはrev, l = reverse_copy(head)を行うには、まだ元のリストを参照してくださいhead持つことができます！

Answer 2

。これはもちろん、dummyを逆のリストの最後のノードにします。次に、dummyから次の要素の値にアクセスしようとします。dummy.nextがNoneであるため、これは明らかに失敗します。

2つ目の例では、リンクにはまったくアクセスしていませんが、値のみです。リストを逆にすると、ノード間のリンクのみが変更され、値は変更されないため、変更を検出することはできません。

更新は私が前と反転後のリストを表示する新しい機能を追加しましたここで何が起こっているのより良い説明するために：

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) 

あなたは出力以下得る上でオリジナルisPalindromeを交換する場合：

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'