【Python】参照先の移り変わりを頑張って理解したい【LeetCode】

7370 ワード
メモ Python Python3 leetcode Python テキストリンク

はじめに

最近LeetCodeというサイトでプログラミングの問題を解き始めました。
しかしながら、さっそく2番目の単純リストを用いた足し算問題でつまずいてしまう始末。
きちんと理解するためにQiitaで自分なりに考えたことをアウトプットしとこう。と思った次第です。
問題へのリンクはこちら

本題

答えを見ながら作った回答

Solution.py
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummyHead = ListNode(0)
        current = dummyHead
        carry = 0
        while(l1 is not None or l2 is not None):
            x = l1.val if l1 is not None else 0
            y = l2.val if l2 is not None else 0

            #足し算の結果と繰り上がりを求める
            total = carry + x + y
            carry = int(total/10)

            #currentを更新
            current.next = ListNode(total%10)
            current = current.next

            #次の位へ移動
            if l1 is not None:
                l1 = l1.next
            if l2 is not None:
                l2 = l2.next
        #最後の計算で繰り上がりがあればそれも反映させる
        if(carry > 0):
            current.next = ListNode(carry)
        return dummyHead.next #なぜdummyHead.nextを返したら答えが求められる？？

頑張って理解する

上記のように書いて提出してみたところ、とりあえず正しく動くプログラムと判定されました。
引っかかったのは、なぜ、dummyHeadは途中で触っていないのに最後に返り値として使えるのか？というところ。
基本的にPythonは参照の代入をするはず。ということは、なにやらオブジェクト同士の参照関係が理解できていない気がする...
動作を理解すべく、順を追って考えてみます。
なお、今回は足し算のところがメインではないので、足し算についての考察はせず、画像内の7,2,8という数値は適当に入れました。ご了承ください。

dummyHead = ListNode(0)
current = dummyHead

まず、この部分。先述したように、Pythonは基本的に参照の代入をします。
そのため、この時点でdummyHeadとcurrentが指し示しているものは同じです。

三項演算、足し算と繰り上がりを求めている部分は特筆すべきことはありません。
続いて以下の部分に注目。

#currentを更新
current.next = ListNode(total%10)
current = current.next

current.nextはNoneでしたが、ここでListNodeが代入されました。
続くcurrent = current.next は、やはり参照の代入です。この部分の関係性としては次のようになります。

dummyHeadは外側のListNodeオブジェクトを指したままであり、current = current.next によって currentの参照先が一段内側のnextに変わります。
このようにcurrentの参照先を変えていきながら、dummyHeadが指し示しているオブジェクトをどんどん改造していくことができます。
最終的に、次のようになります。

この結果、一番外側のlistNodeを指しているdummyHeadを最後にreturnしてやれば、計算結果が格納されたオブジェクトを返すことが可能になります。

おわりに

グラフ形式で作図しようと思ったのですが、ListNodeクラスの入れ子構造を表現できるブロックを使って作図してみました。
アルゴリズム自体は簡単だったのに、私の想像力の欠如によって詰まってしまった問題でした。
精進せねば。。。