leetcode,アルゴリズム,class

Question

アルゴリズムの問題をpythonで解いています。leetcodeのサイトでアルゴリズムの問題を解いているのですが、問題の前提として渡されている2つのクラスが何を表現しているのか分からずに困っております。
https://leetcode.com/problems/merge-two-sorted-lists/が問題のページです。問題の要求は、整数が要素として含まれる2つのリストがあり、それら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 mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
以上が最初から与えられているコードです。l1,l2が上述のリストに当たると思うのですが、l1、l2のあとのコロンの意味、そしてコロンの後ろのListNodeがどのように働いているのかが分からず悩んでおります。
https://leetcode.com/problems/merge-two-sorted-lists/discuss/?currentPage=1&orderBy=hot&query=
上のリンクはたくさんの人の回答が載っており、正しく動くものばかりです。よろしくお願いいたします。

Answer 1

型アノテーションです。

• Pythonではじまる、型のある世界 - Qiita
• Pythonの関数アノテーションと型ヒント、typingモジュール | note.nkmk.me

Pythonは動的型付けを行いますが、
コードを組む際には型が静的に（実行前に）定まっている方が都合が良いです。

Comments

[fjhfhheavnffrqi]

アノテーションについて教えていただき大変ありがとうございます。特にオブジェクト型、クラスのコードを理解するのが困難なものです。質問内容が一部大きくなっているのを修正いたしました。よろしければ上述のclass ListNodeがどういったことをあらわしているのか教えていただけると大変うれしく思います。リストであるl1,l2にアノテーションが付いているのでおそらくclass ListNodeはリストに関係があると思うのですが…

[LouiS0616]

単方向の連結リストに見えます。
実際 Definition for singly-linked list. と書いてありますし。

[fjhfhheavnffrqi]

回答いただき本当にありがとうございます。
自分はリストというと[]で囲まれたものを思い浮かべてしまいますが、class ListNodeはどのようにリストを表現しているのかわかりません、おそらくvalとnextの2つの変数が関係していると思うのですが、仕組みを考えてもどうしても見えてこないのです。その点に関しても教えていただけることがあれば嬉しいです、どうかよろしくお願いいたします。

[LouiS0616]

リンク先、左側に □→□→□ みたいな図があると思います。
これがまさに単方向の連結リストで、各ノード（要素）は ①自分自身の値 ②次の要素の場所 を知っています。Pythonの場合 ①自分自身の値 ②次の要素 だと解釈しても問題ないでしょう。これがvalとnextの正体です。

> 自分はリストというと[]で囲まれたものを思い浮かべてしまいます

一言でリストと言っても様々な実装がありますので、組み込みリストを想像すること自体は間違いでは無いです。（Pythonの組み込みリストはLinkedListではなくArrayListだったような気がします）

> 仕組みを考えてもどうしても見えてこないのです。

連結リストについては、私がここで語るよりネット上の情報に頼った方が良いと思います。
画像や動画を交えて解説しているものもある筈です。

[fjhfhheavnffrqi]

連結リストの存在を知らなかったため、そこから解説していただくことになってしまい申し訳ありません。しかし自分の疑問をまさに解消できる回答をいただき本当に感謝しております。勝手ながらフォローさせていただきました、よろしくお願いします。

Answer 2

連結リストについて、一言。

アルゴリズムを勉強しているということですので、pythonなどの最近の言語で提供されているリストや辞書(連想リスト)・キューなどのデータ構造は、プログラミング言語としては高度な物であって、Cあたりの言語では用意されないものであることは知っておいたほうがいいと思います。

そのような構造を表現したり監視したりするための手順やデータ構造、ようするに'アルゴリズ'がいろいろと考えられていて、それを勉強しようとしているということなのです。

Comments

[fjhfhheavnffrqi]

回答大変ありがとうございます、教えていただいたことは知りませんでした。覚えておきたいと思います。今はアウトプットとインプット両方をしたくてアルゴリズムの問題を解いています。他にもデータ構造の問題もleetcodeにあるのでそのうち取り組もうと思っています。今は完全に初心者なので、そういう問題の数をこなして上達していくつもりです、回答大変ありがとうございました