JAVA初窥-DAY 12

JAVA初窥-DAY 12

ヘッドレス一方向非循環チェーンテーブルの拡張

逆数K

チェーンテーブルソート

判断回文

判定ループ

判定ループ継続

パージ繰返し

ヘッドレス一方向非循環チェーンテーブルの拡張
最後からK番目
出力逆数K番目のノード

    public Node back(int k){
     //     K   
        Node slow = this.head;
        Node fast = this.head;
        if (k<1||k>size){
     
        	System.out.println("      K");
            return null;
        }
        for (;k>0;k--){
     
            fast=fast.next;
        }
        for (;fast != null;){
     
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }

チェーンテーブルのソート
xより小さいものは前に、残りは後ろに置きます.

public void sort(int x){
     //  ：  x    ，      
    if (head ==null){
     
        return;
    }
    Node af = null;
    Node ae = null;
    Node bf = null;
    Node be = null;
    Node cur = this.head;
    for (;cur !=null;cur=cur.next){
     
        if (cur.val < x){
     
            if (af == null){
     
                af = cur ;
                ae = cur ;
            }else {
     
                ae.next = cur;
                ae = cur;
            }
        }else {
     
            if (bf == null){
     
                bf = cur ;
                be = cur ;
            }else {
     
                be.next = cur;
                be = cur;
            }
        }
    }
    be.next=null;
    if (af == null){
     
        this.head = bf;
        return;
    }
    if (bf == null){
     
        ae.next = null;
        this.head = af;
        return;
    }
    ae.next=bf;
    return;
}

判断文
回文構造:12321、123321、181など

public boolean plalindrome(){
     
    Node prev =midNode();
    Node cur = prev.next;
    Node curNext = cur.next;
    for (;curNext!=null;){
     
        cur.next = prev;
        prev = cur;
        cur = curNext;
        curNext = curNext.next;
    }
    cur.next = prev;
    prev = this.head;
    for (;prev != cur && prev.next != cur ;){
     
        if (cur.val != prev.val){
     
            return false;
        }
        prev=prev.next;
        cur = cur.next;
    }
    if (cur.val != prev.val){
     
        return false;
    }
    return true;
}

判断にループがある

public boolean ring(){
     
    Node fast = this.head;
    Node slow = this.head;
    for (;fast!=null && fast.next!=null;){
     
        fast=fast.next.next;
        slow=slow.next;
        if (slow == fast){
     
            break;
        }
    }
    if (fast == null || fast.next==null){
     
        return false;
    }
    return true;
}

ループ継続の判断
ループがあると判断してループを出力するエントリノード

public int ringB(){
     
    Node fast = this.head;
    Node slow = this.head;
    for (;fast!=null && fast.next!=null;){
     
        fast=fast.next.next;
        slow=slow.next;
        if (slow == fast){
     
            break;
        }
    }
    if (fast == null || fast.next==null){
     
        return -1;
    }
    fast = this.head;
    for (;fast != slow;){
     
        fast = fast.next;
        slow = slow.next;
    }
    return slow.val;
}

重複除外
順序付きチェーンテーブル重複コンテンツを消去し、重複コンテンツを保持しない

public void clear() {
     
    Node cur = this.head;
    for (;cur.next!=null;){
     
        if (cur.val == cur.next.val){
     
            del(cur.val);
        }
        cur=cur.next;
    }
}