チェーンテーブル要素の削除:歩哨ノード

目次

チェーンテーブル要素削除:歩哨ノード

83. ソートチェーンテーブルの重複要素Iを削除する

題名説明

コード実装

複雑度分析

203.チェーンテーブル要素の除去

題名説明

哨兵ノードの利用

コード実装

複雑度分析

82.ソートチェーンテーブルの重複要素を削除するII

題名説明

コード実装

複雑度分析

チェーンテーブル要素の削除:歩哨ノード
83.ソートチェーンテーブルの重複要素Iを削除する
タイトルの説明
ソートチェーンテーブルを指定し、重複するすべての要素を削除して、各要素が一度だけ表示されるようにします.
これは星を描く簡単な問題で、難易度はあまり高くありません.注意すべき点は次のとおりです.

チェーンテーブルが順番に並んでいるので、このような場合は、次のものが前のものと等しいかどうかを見て、繰り返し要素を探しましょう.

もう一つ、削除された要素は最初のノードではありません.

コード実装

    public static ListNode deleteDuplicates(ListNode head){
        //      
        ListNode currNode = head;
        //           ，    next      next
        while(currNode!=null&&currNode.next!=null){
            if(currNode.val==currNode.next.val){
                currNode.next = currNode.next.next;
            }else{
                //      ，        
                currNode = currNode.next;
            }
        }
        return head;
    }

複雑度分析

時間複雑度:O(n)、nはノード個数

空間複雑度:O(1)

203.チェーンテーブル要素の除去
タイトルの説明
チェーンテーブルの値valに等しいすべてのノードを削除します.
私の初歩的な考えは:

2つの前後のポインタを定義、後のポインタは現在の状態curr、前のポインタは前のprevを表す.

現在の値がvalであればprev.next=curr.next,後方遍歴:curr=curr.next.

これにより、val値を表すノードが削除される.

もちろん、削除する複数の要素がヘッダノードに現れることは考えていませんが、これを考えると、哨兵ノードのメリットが現れます.
哨兵ノードの利用
削除する1つ以上のノードがチェーンテーブルの頭部にある場合、歩哨ノードを使用してチェーンテーブルを標準化することができ、チェーンテーブルが空でなくても、頭がなくなくなくても、挿入と削除の操作を簡素化することができます.

疑似ヘッドとして哨兵ノードを定義できる.sentinel:ListNode sentinel = new ListNode(0);

「真頭」headを指さす:sentinel.next = head;

2つのポインタを定義し、1つは前方ポインタprev、1つは現在のポインタcurrとする.

currの値が指定値であれば、prevの次のノードが現在のノードの次の系ノードを指すようにする.

currの値が指定値でなければ、前のノードを表すポインタprevを現在のポインタに向けさせる.

currは常に後ろを回っている.

最後にsentinelに戻る.next.(prevとsentinelは同じアドレスを指し、prevはチェーンテーブルの操作を完了した)

コード実装

   public ListNode sentinelRemove(ListNode head,int val){
       //      ，  head
       ListNode sentinel = new ListNode(0);
       sentinel.next = head;
       //      ，        ，    head
       ListNode prev = sentinel;
       ListNode curr = head;
       while(curr!=null){
           if(curr.val == val){
               //          ，        next       
               prev.next = curr.next;
           }else{
               //        
               prev = curr;
           }
           //      
           curr = curr.next;
       }
       //           
       return sentinel.next;
   }

複雑度分析

時間複雑度:O(n)

空間複雑度:O(1)

82.並べ替えチェーンテーブルの重複要素IIを削除する
タイトルの説明
並べ替えチェーンテーブルを指定し、重複する数値を含むすべてのノードを削除し、元のチェーンテーブルに重複していない数値だけを保持します.
同じようにチェーンテーブルの重複要素を削除して、最初の問題は1つ残しておけばいいので、この問題の意味は1つ残さないことです.次の点に注意してください.

チェーンテーブルは並べ替えられている.

削除したノードはヘッダノードである可能性がある.

この問題は、哨兵ノードを利用することができます.
コード実装

    public ListNode deleteDuplicates(ListNode head) {
        //      ，  head
        ListNode sentinel = new ListNode(0);
        sentinel.next = head;
        ListNode prev = sentinel,curr = head;
        //             
        while(curr!=null&&curr.next!=null){
            //          
            if(curr.val == curr.next.val){
                //    ，  curr       
                int val = curr.val;
                while(curr!=null&&curr.val==val){
                    curr = curr.next;
                }
                //      
                prev.next = curr;
            }else{
                //      
                //          
                prev = curr;
                curr = curr.next;
            }
        }
        return sentinel.next;
    }

複雑度分析

時間複雑度:O(n)

空間複雑度:O(1)

参照リンク:https://leetcode-cn.com/problems/remove-linked-list-elements/solution/yi-chu-lian-biao-yuan-su-by-leetcode/
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/solution/shan-chu-pai-xu-lian-biao-zhong-de-zhong-fu-yuan-s/