【Leetcodeブラシ問題まとめ】(一)チェーンテーブル逆順

タイトル:
先頭のチェーンテーブルを指定し、逆シーケンスで出力します.
例:
入力:head->1->2->3->4->None
出力:head->4->3->2->1->None
   
方法一:その場で逆序
【注意】:1チェーンテーブルの使用は、headノードを与えるだけでチェーンテーブル全体を連結することができます.
2チェーンテーブルの最初のノードはヘッダノードです.ヘッダノードのデータドメインが空です.チェーンテーブルのヘッダノードとは、ヘッダノードを除く最初のノードを指す.
3チェーンテーブルの末尾ノードは最後のノードであり、チェーンテーブルの末尾ノードのポインタドメインは空である.(nail.next=None)
分析:
3つのポインタ,pre,cur,nextはそれぞれ前置,現在,後置ポインタを表し,その後絶えず後方にスライドし,現在のノードの本来の後置ノードを指すポインタが前置ノードを指すようにする.このようにするにはいくつかの注意点があります.
まず、現在のノードのポインタを動かす前に、必ず現在のノードのポインタをメモしてnext=cur.nextを保存します.そうしないと、現在のノードcurのポインタを動かすと、後置ノードnextが見つかりません.
次に、チェーンテーブルのヘッダノードは特殊な処理が必要です.preノードがないので、ループが走れません.手動で接続し、ポインタドメインを空にしてテールノードとします.
最後に、curが最後のノードである場合、後置ノードがないため、前のノードpreを手動で指さす必要があるため、特殊な処理も必要である.
最後の最後に、チェーン時計のヘッドノードhead.最後のノードを指すと完了します.
キーコード:

def Reverse(head):
    if head ==None or head.next == None:    #        (     ，          )
        return 0

    pre = None             #                       
    cur = None 
    next = None

    cur = head.next        #      
    next = cur.next        # cur        
    cur.next = None        #       
    
    pre = cur              #    
    cur = next
    
    while(cur.next != None):      
        next = cur.next             # cur        
        
        cur.next = pre              # cur  pre

        pre = cur                   #    
        cur = next
    
    cur.next = pre                  #        （        pre）
    head.next = cur                 #         

パフォーマンス分析:
時間複雑度O(n)遍歴一次チェーンテーブル
空間複雑度O(1)
方法2:挿入法
そうにゅうほう