今日からLeetcodeをやっていく!
今日から毎日Leetcodeをやろうと思う。
1問目はLinked List cycle
https://leetcode.com/problems/linked-list-cycle/submissions/1379361223/
目次
LinkedList
とは何か?
まずは、LinkedListが何かを知らなかったので調べた。
class LinkedList:
class Node:
def __init__(self, payload):
self.payload = payload
self.next = None
def __init__(self):
self.head = None
def addNode(self, newpayload):
newnode = LinkedList.Node(newpayload)
if self.head == None:
self.head = newnode
return
else: #最後のノードに連結するケース
runner = self.head
while runner.next != None:
runner = runner.next
runner.next = newnode
links = LinkedList()
links.addNode(26)
links.addNode(99)
links.addNode(127)
links.addNode(42)
links.addNode(367)
コードの動き方
このコードは階層構造で以下のようなリンクドリストを構築する。
- Node(26)
- payload = 26
- next = Node(99)
- payload = 99
- next = Node(127)
- payload = 127
- next = None
links = LinkedList()
Linked Listオブジェクトが作られる。
この時Linked List.init も動き self.head(= LinkedList.head)=Noneと設定される
links.addNode(26)
addNode関数が動く。
newnode = LinkedList.Node(newpayload)によりnewnodeにNodeクラスが代入されNode(26)が作られる。またこの時Node.initも動きself.payload = newpayload = 26, self.next = Noneとなる。
次にself.head = None なので self.head = newnode = Node(26)が代入される。
links.addNode(99)
addNode関数が動く
newnode = LinkedList.Node(newpayload)によりnewnodeにNodeクラスが代入されNode(99)が作られる。
次にself.head = Node(26) != None なのでelseとなる。
runner = self.head = Node(26) となる。
runner.next = Node(26).next = None なのでrunner.nextにnewnodeが代入される。つまりNode(99)が代入される。
ここでNode()はpayload = 26, next = Node(99) を変数にもつくクラスとなる。
links.addNode(127)
同様に行いNode(99).next = Node(127)となる。
LinkedListとArrayListの違い
-
LinkedList
- 順序を持たない
- 要素がリンクで繋がっている
- 途中の要素を削除するスピードが速い
- 特定の要素にアクセスするスピードが遅い
-
ArrayList
- 順序を持つ
- 要素が順序で繋がっている
- 要素を削除するスピードが遅い
- 特定の要素にアクセスするスピードが速い
Linked List Cycle
Linked List Cycleの解法を解説してくれるものがあったのでこのコードを使ってみるとうまくいった。Fast nodeとSlow nodeは知らないと思いつかなそう。
Leet code は classの内容を実装するだけで良い。
Atcoderだとinputもいちいち書かなきゃいけなかったので入出力も書かなきゃいけないものかと思ってちょっと調べた
明日もやる。