データ構造
LeetCodeにおける連結リストの各ノードの定義
・解答欄にクラスが定義されている ※実際にはコメントアウトされている
1 2 3 4 5 |
# Definition for singly-linked list. class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next |
・inputはリスト型に見える
1 |
[1,2,3,4,5] |
・↑こちらのinputを解答欄でprintしてみると以下のように出力される
1 |
ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: ListNode{val: 3, next: ListNode{val: 4, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}}}}} |
分解してみると↓のようになっており、連結リストの先頭は2番目以降の要素を抱えた入れ子構造のようになっている
ListNode(1)のvalは1,nextはListNode(2)のval
ListNode(2)のvalは2,nextはListNode(3)のval
ListNode(3)のvalは3,nextはListNode(4)のval
ListNode(4)のvalは4,nextはListNode(4)のval
ListNode(5)のvalは5,nextはNone
連結リストの作成
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#連結リストの各ノードの定義 class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next #リストから連結リストを作成 class Solution(object): def test(self, head: ListNode) -> ListNode: list = [1,2,3,4,5] _ = ListNode(0) for i in list: _.next = ListNode(i) _= _.next |
何か違う気がする。要確認
連結リストの中央の要素の取得
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#連結リストの各ノードの定義 class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next #中央の要素の取得 class Test: def getMid(self, head): #一度に1個、2個進む2種類のポインタを作成 slow, fast = head, head.next #fast、fastの次のノードがある限り繰り返す while fast and fast.next: #slowポインタは次の要素へ slow = slow.next #fastポインタは次の次の要素へ fast = fast.next.next #slowポインタを返す return slow |
slowポインタは毎回1つ、fastポインタは毎回2つ進むことで、
fastポインタが連結リストの終端に到着したときに、slowポインタはちょうど連結リストの中央の要素を持っていることになる。
二分木
LeetCodeにおける二分木の各ノードの定義
1 2 3 4 5 6 |
# Definition for a binary tree node. class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right |
コメント