Linked Listのコードが解読が出来ない

Question

leetcodeの「206. Reverse Linked List」問題について

回答がわからず検索したところ下記のコードに行き着きましたが、解読できず困っています。
※LinkedListというよりpythonの仕様理解不足の気はしていますが

最初のwhile文はheadをstackに格納するため（後からpop()で逆順取得するため）というのは
理解できましたが、後半のwhile文でcurとstackの操作しか行われておらず、なぜheadの値が書き変わっているのか？（どこで参照が渡っている？）がわからずつまづいています。

実装したい仕様
inputしたListNode型を逆順にして返す
(ex.)　Input: head = [1,2,3,4,5]　　Output: [5,4,3,2,1]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return None

        stack = []

        while head.next:
            stack.append(head)
            head = head.next

        while stack:
            cur = stack.pop()
            cur.next.next = cur
            cur.next = None

        return head

Comments

[ppaul]

再帰関数を使えば5行で書けて、ずっとわかりやすいですね。
こういう出来の悪い解法でも読めないのは困りますが、もっと良い解法を探しましょう。

Answer 1

絵にかいて動作を１つずつ確認してみることをお勧めします。
code を説明していくと
while head.next: 終了後 head は、最後の ListNode です。
while stack: の最初の cur = stack.pop() で cur に最後の１つ前の ListNode を持って来ています。
cur.next は最後の ListNode（つまり現在の head ）ですので
cur.next.next = cur で head.next に最後の１つ前の ListNode を入れています。
cur.next = None で最後の１つ前の ListNode の next を None にしています。
これで、逆順並び替えの最初の接続が完了ですね。

個人的には、保守性の悪い code に思えます。
すべて stack に保存して繋ぎ直す次のような code がわかりやすいでしょう。

        while head:
            stack.append(head)
            head = head.next

        cur = head = stack.pop()
        while stack:
            cur.next = stack.pop()
            cur = cur.next
            cur.next = None

一旦、最後の ListNode を stack に積んでからすぐ pop する無駄が気になるのであれば、最後の ListNode は stack に積まずに次のようにした方が１行増えてもわかりやすいでしょうね。

        while head.next:
            stack.append(head)
            head = head.next

        cur = head
        while stack:
            cur.next = stack.pop()
            cur = cur.next
            cur.next = None

参考に再帰を使ったコードも提示しておきます。

    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return None
        self.head = head
        if head.next:
            self.reverseList(head.next)
            head.next.next = head
            head.next = None
        return self.head

再帰より stack 使わず単純に while で繋ぎ直す方が簡単ですね。こちらも参考に提示しておきます。
Python の代入文は複数代入が可能で右辺を先に評価するため繋ぎ直し処理を４行で実装できます。

    def reverseList(self, head: ListNode) -> ListNode:
        pre, cur = None, head
        while cur:
            cur.next, pre, cur = pre, cur, cur.next
        return pre

Comments

[mns]

>絵にかいて動作を１つずつ確認
これでやっと理解できました。
連結リストはじめ、アルゴリズムの知見が無いのに、python不慣れで参考コードの品質も確認出来ず。。。
（メインJavaですがleetCodeではpython推奨と聞いて練習中）
他の方も丁寧に回答いただきましたが、改善コードと再起法についてもご丁寧にありがとうございます。

Answer 2

pythonの変数は参照渡しなので元のListNodeとstackに入れたListNodeとcurに取り出したListNodeは全く同じものを指します。
どれかを編集したら他で参照してる同じListNode全てが書き変わる訳です。

例えば

a = [['foo', 'bar'], [1, 2]]
b = a[0]
b[0] = 'hoge'

print(a) #-> [['hoge', 'bar'], [1, 2]]

となります。

Answer 3

1つめのwhileの中でheadを残りの先頭に貼り替えていますよね。ということは、whileを回りきった後では、headはリストの最後のものを保持しています。stackの先頭に入っているのも同じものです。

2つめのwhileでstackの中身を順に(結果としてもととは逆順に)つないでいますが、headは書き換えていないので、想定どおり、逆順になったリストの先頭を指していることになります。