連結リストの要素削除

例：入力：head = [1,2,6,3,4,5,6], val = 6 出力：[1,2,3,4,5]

連結リストの設計

連結リストクラスで以下の機能を実装します：

get(index)：連結リストのindex番目のノードの値を取得します。インデックスが無効な場合は-1を返します。
addAtHead(val)：連結リストの最初の要素の前に値がvalのノードを追加します。挿入後、新しいノードが連結リストの最初のノードになります。
addAtTail(val)：値がvalのノードを連結リストの最後の要素に追加します。addAtIndex(index,val)：連結リストのindex番目のノードの前に値がvalのノードを追加します。indexが連結リストの長さに等しい場合、ノードは連結リストの末尾に追加されます。indexが連結リストの長さより大きい場合は、ノードは挿入されません。indexが0より小さい場合は、先頭にノードを挿入します。deleteAtIndex(index)：インデックスindexが有効な場合、連結リストのindex番目のノードを削除します。

連結リストの反転

例：入力: 1->2->3->4->5->NULL 出力: 5->4->3->2->1->NULL

まず連結リストクラスを定義します

class リストノード():
    def __init__(self,値=0,次=None):
        self.値 = 値
        self.次 = 次

考え方：1.n番目のノードの値を取得：nの値に到達するためにどうループすればよいか、いつループを停止するか、インデックスが有効な場合、毎回現在のポインタを1つ後ろに移動します

考え方：2.solutionクラス内に配列から連結リストを作成するメソッドを定義し、さらに連結リストを出力するメソッドを定義すれば、入出力がより簡潔になります

class 解決策:

    ## 連結リストを設計する過程で、データ領域とポインタ領域に加えて、連結リストのサイズという属性も必要です
    def __init__(self):
        self.ダミーノード = リストノード() # すべてのメソッドのために仮想頭ノードを構築
        self.サイズ = 0

    ## リストから連結リストを作成し、連結リストのサイズを取得
    def 連結リスト作成(self,配列:リスト[int])->リストノード:
        ヘッド = リストノード(値=配列[0])
        self.ダミーノード.次 = ヘッド
        self.サイズ = 1
        現在 = ヘッド
        for i in range(1,len(配列)):
            現在.次 = リストノード(値=配列[i])
            現在 = 現在.次
            self.サイズ += 1
        return ヘッド

    def ノード出力(self,ヘッド):
        if ヘッド is None:
            return
        現在 = ヘッド
        while 現在:
            print(現在.値, end="->")
            現在 = 現在.次
        print('null')

1. 連結リストの要素削除

def 要素削除(self, ヘッド:オプション[リストノード], 値: int) -> オプション[リストノード]:
    # 削除プロセスを簡化するために仮想頭ノードを作成
    ダミーヘッド = リストノード(次=ヘッド)
    
    # リストを走査して値がvalのノードを削除
    現在 = ダミーヘッド
    while 現在.次:
        if 現在.次.値 == 値:
            現在.次 = 現在.次.次
        else:
            現在 = 現在.次
    
    return ダミーヘッド.次

2. インデックスがindexのノードの値を取得

def 値取得(self, ヘッド:オプション[リストノード], 目標:int)->int:
    現在 = ヘッド # ポインタを頭ノードから開始
    # 現在のノードが最後のノードではない、リストが空ではない
    if 目標 < 0 or 目標 > self.サイズ:
        return -1
    else:
        while(目標-1):
            現在 = 現在.次
            目標 -= 1
        return 現在.値

3. 先頭ノードに挿入

def 先頭挿入(self, ヘッド:オプション[リストノード], 値:int)->リストノード:
    現在 = self.ダミーノード # ポインタを仮想頭ノードから開始
    新ノード = リストノード(値=値, 次=ヘッド)
    現在.次 = 新ノード
    self.サイズ += 1
    return 現在.次

4. 末尾ノードに挿入

def 末尾挿入(self, ヘッド:オプション[リストノード], 値:int)->リストノード:
    現在 = self.ダミーノード
    while(現在.次):
        現在 = 現在.次
    
    現在.次 = リストノード(値=値, 次=現在.次)
    self.サイズ += 1
    return ヘッド

5. インデックスindexに挿入

def 挿入(self, ヘッド:オプション[リストノード], 位置:int, 値:int)->リストノード:
    現在 = self.ダミーノード # 0番目のノードと見なす
    if 位置 < 0:
        self.先頭挿入(ヘッド, 値)
    elif 位置 > self.サイズ:
        self.末尾挿入(ヘッド, 値)
    else:
        while(位置-1):
            現在 = 現在.次
            位置 -= 1
        
        新ノード = リストノード(値=値, 次=現在.次)
        現在.次 = 新ノード
        self.サイズ += 1
        return ヘッド

6. インデックス位置のノードを削除

def 削除(self, ヘッド:オプション[リストノード], 位置:int)->リストノード:
    現在 = self.ダミーノード # 0番目のノードと見なす
    if 位置 < 0 or 位置 >= self.サイズ:
        return ヘッド
    
    # 削除位置の直前のノードまで移動
    for _ in range(位置):
        現在 = 現在.次
    
    # ノードを削除
    削除ノード = 現在.次
    現在.次 = 削除ノード.次
    self.サイズ -= 1
    return ヘッド

7. 連結リストの反転

# 連結リストを反転するメソッド
def 反転(self, ヘッド:オプション[リストノード])->オプション[リストノード]:
    # 反転：現在ノードの次のノードの次を現在ノードに指させる
    前 = None
    現在 = ヘッド
    # 次のnextを変更すると、元のノード間のリンクが切断されるため、事前に次のノードを保存する必要がある
    while (現在):
        一時 = 現在.次
        現在.次 = 前
        前 = 現在
        現在 = 一時
    return 前

関数呼び出しの例

if __name__ == "__main__":
    配列 = [3,3,1,2,5,3,5,6,3,3,7,3]
    位置 = 4  # 挿入位置
    値 = 3   # 挿入値
    s = 解決策()
    l = s.連結リスト作成(配列)
    # 作成した連結リスト
    s.ノード出力(l)
    
    # 値の取得
    # 取得値 = s.値取得(l, 位置)
    # print(取得値)
    
    # 先頭への挿入
    # l1 = s.先頭挿入(l, 値)
    
    # 末尾への挿入
    # l2 = s.末尾挿入(l, 値)
    
    # 指定位置への挿入
    # l3 = s.挿入(l, 位置, 値)
    
    # 連結リストの反転
    l4 = s.反転(l)
    
    # s.ノード出力(l1)
    # s.ノード出力(l2)
    # s.ノード出力(l3)
    s.ノード出力(l4)