問題 連結リストとある値xが与えられたときにxの前にxよりも小さい値が、後にxよりも大きい値が来るようにする。 考え方 xよりも小さい数のリストと大きい数のリストを作り、最後にくっつける。 時間計算量はO(N) コード例 import random class Node(): def …

問題 間のnodeだけ与えられたときにそれを削除する 考え方 削除したいnodeが次のnodeに当たるように書き換えれば良い コード例 class Node(): def __init__(self, d): self.data = d self.next = None def appendToTail(self, d): end = Node(d) n = self wh…

問題 単方向連結リストにおいて末尾から数えてk番目の要素を返す。 考え方 連結リストの長さがわからないという前提で考える。 ランナーテクニックを利用する。 ２つのポインタを用意する。 前からk番目からスタート 初めからスタート １つ目のポインタが最…

問題 ソートされていない連結リストから重複した要素を削除する。 考え方 一度出てきた値はhash tableに保存しておいて、もう一度出たら削除する。 一度リスト全体を見ればいいので、時間計算量はO(N) コード例 # 双方向連結リスト class LinkedList(): def …