一.棧

1.getmin棧

class MyStack{
    public MyStack(Stack<Integer> stackData, Stack<Integer> stackMin) {
        this.stackData = stackData;
        this.stackMin = stackMin;
    }
    private Stack<Integer> stackData; //存所有值的
    private Stack<Integer> stackMin;//始終存存的是最小值
    public void push(int num){
     if(this.stackMin.empty()){
         this.stackMin.push(num);
     }else if (num< this.getMin()){
         this.stackMin.push(num);
     }
     this.stackData.push(num);
    }
    public int pop(){
        if(this.stackData.empty()){
            throw new RuntimeException("empty stack");
        }
        int value=this.stackData.pop();
        if(this.getMin()==value){
            this.stackMin.pop();
        }
        return value;
    }
    public int getMin(){
        if(this.stackMin.empty()){
            throw new RuntimeException("empty stack");
        }
        return  this.stackMin.peek();

    }
}

image.gif

2.貓狗隊列

public static class Pet {
        private String type;
        public Pet(String type) {
            this.type = type;
        }

        public String getPetType() {
            return this.type;
        }
    }

    public static class Dog extends Pet {
        public Dog() {
            super("dog");
        }
    }

    public static class Cat extends Pet {
        public Cat() {
            super("cat");
        }
    }

    public static class PetEnterQueue {
        private Pet pet;
        private long count;

        public PetEnterQueue(Pet pet, long count) {
            this.pet = pet;
            this.count = count;
        }

        public Pet getPet() {
            return this.pet;
        }

        public long getCount() {
            return this.count;
        }

        public String getEnterPetType() {
            return this.pet.getPetType();
        }
    }

    public static class DogCatQueue {
        //queue的方法
        //尾部添加
        //boolean add(E e);
        //boolean offer(E e);
        //他們的共同之處是建議實現(xiàn)類禁止添加 null 元素，否則會報空指針 NullPointerException；
        //不同之處在于 add() 方法在添加失敗（比如隊列已滿）時會報 一些運行時錯誤 錯；而 offer() 方法即使在添加失敗時也不會奔潰，只會返回 false。
        //刪除返回頭部
        //E remove();
        //E poll();
        //當(dāng)隊列為空時 remove() 方法會報 NoSuchElementException 錯; 而 poll() 不會奔潰，只會返回 null。
        //返回頭部
        //E element();
        //E peek();
        //當(dāng)隊列為空時 element() 拋出異常；peek() 不會奔潰，只會返回 null。
        private Queue<PetEnterQueue> dogQ;
        private Queue<PetEnterQueue> catQ;
        private long count;

        //1.add方法將cat類或dog類的實例放入隊列中
        //2.pollAll方法，將隊列中所有的實例按照進隊列的先后順序依次彈出；
        //3.pollDog方法，將隊列中dog類的實例按照進隊列的先后順序依次彈出；
        //4.pollCat方法，將隊列中cat類的實例按照進隊列的先后順序依次彈出；
        //5.isEmpty方法，檢查隊列中是否還有dog或cat的實例；
        //6.isDogEmpty方法，檢查隊列中是否有dog類的實例；
        //7.isCatEmpty方法，檢查隊列中是否有cat類的實例。
        public DogCatQueue() {
            this.dogQ = new LinkedList<PetEnterQueue>();
            this.catQ = new LinkedList<PetEnterQueue>();
            this.count = 0;
        }

        public void add(Pet pet) {
            if (pet.getPetType().equals("dog")) {
                this.dogQ.add(new PetEnterQueue(pet, this.count++));
            } else if (pet.getPetType().equals("cat")) {
                this.catQ.add(new PetEnterQueue(pet, this.count++));
            } else {
                throw new RuntimeException("err, not dog or cat");
            }
        }

        public Pet pollAll() {
            if (!this.dogQ.isEmpty() && !this.catQ.isEmpty()) {
                //總是數(shù)量多的那個后入隊列的
                if (this.dogQ.peek().getCount() < this.catQ.peek().getCount()) {
                    return this.dogQ.poll().getPet();
                } else {
                    return this.catQ.poll().getPet();
                }
            } else if (!this.dogQ.isEmpty()) {
                return this.dogQ.poll().getPet();
            } else if (!this.catQ.isEmpty()) {
                return this.catQ.poll().getPet();
            } else {
                throw new RuntimeException("err, queue is empty!");
            }
        }

        public Dog pollDog() {
            if (!this.isDogQueueEmpty()) {
                return (Dog) this.dogQ.poll().getPet();
            } else {
                throw new RuntimeException("Dog queue is empty!");
            }
        }

        public Cat pollCat() {
            if (!this.isCatQueueEmpty()) {
                return (Cat) this.catQ.poll().getPet();
            } else
                throw new RuntimeException("Cat queue is empty!");
        }

        public boolean isEmpty() {
            return this.dogQ.isEmpty() && this.catQ.isEmpty();
        }

        public boolean isDogQueueEmpty() {
            return this.dogQ.isEmpty();
        }

        public boolean isCatQueueEmpty() {
            return this.catQ.isEmpty();
        }

    }

3.一個棧實現(xiàn)另外棧的排序

public static void sortStackByStack(Stack<Integer> stack) {
        Stack<Integer> help = new Stack<Integer>();
        while (!stack.isEmpty()) {
            int cur = stack.pop();
            while (!help.isEmpty() && help.peek() < cur) {
                stack.push(help.pop());
            }
            help.push(cur);
        }
        while (!help.isEmpty()) {
            stack.push(help.pop());
        }
    }

二.鏈表

1.print 2個有序鏈表的公共部分

class Node{
    public int value;
    public Node next;
    public Node(int data){
        this.value=data;
    }
}
public class NodeTest {
    public void printCommonPart(Node head1,Node head2){
        while(head1!=null&&head2!=null){
            if (head1.value<head2.value){
                head1=head1.next;
            }else if (head1.value>head2.value){
                head2=head2.next;
            }else{
                System.out.println(head1.value);
                head1=head1.next;
                head2=head2.next;
            }
        }
    }
}

2.單雙鏈表刪除倒數(shù)第k個節(jié)點

//單
//類似差值    
public static Node removeLastKthNode(Node head, int lastKth) {
        if (head == null || lastKth < 1) {
            return head;
        }
        Node cur = head;
        while (cur != null) {
            lastKth--;
            cur = cur.next;
        }
        if (lastKth == 0) {
            head = head.next;
        }
        if (lastKth < 0) {
            cur = head;
            while (++lastKth != 0) {
                cur = cur.next;
            }
            cur.next = cur.next.next;
        }
        return cur;
    }
//棧
//雙指針
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;
        // 讓快指針先走k步，和慢指針相差k個距離
        for (int i = k; i > 0; i--) {
            fast = fast.next;
        }

        // 此時讓慢指針和快指針同時走，知道快指針到達鏈表末尾為null時，慢指針就在倒數(shù)第k個位置上了
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 直接返回慢指針即為答案
        return slow;
    }
}

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;

        // 讓快指針先走k步，和慢指針相差k個距離
        for (int i = k; i > 0; i--) {
            fast = fast.next;
        }

        // 此時讓慢指針和快指針同時走，知道快指針到達鏈表末尾為null時，慢指針就在倒數(shù)第k個位置上了
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 直接返回慢指針即為答案
        return slow;
    }
}

//作者：linzeliang1222
//鏈接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/solution/jian-zhi-offer-22-lian-biao-zhong-dao-sh-ixsa/
//來源：力扣（LeetCode）
//著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

    public static class DoubleNode {
        public int value;
        public DoubleNode last;
        public DoubleNode next;

        public DoubleNode(int data) {
            this.value = data;
        }
    }

    public static DoubleNode removeLastKthNode(DoubleNode head, int lastKth) {
        if (head == null || lastKth < 1) {
            return head;
        }
        DoubleNode cur = head;
        while (cur != null) {
            lastKth--;
            cur = cur.next;
        }
        if (lastKth == 0) {
            head = head.next;
            head.last = null;
        }
        if (lastKth < 0) {
            cur = head;
            while (++lastKth != 0) {
                cur = cur.next;
            }
            DoubleNode newNext = cur.next.next;
            cur.next = newNext;
            if (newNext != null) {
                newNext.last = cur;
            }
        }
        return head;
    }

3.刪除鏈表的中間節(jié)點和a/b處的節(jié)點
4.反轉(zhuǎn)單向和雙向鏈表
5.反轉(zhuǎn)部分單向鏈表
6.環(huán)形單鏈表約瑟夫
7.判斷一個表是否是回文結(jié)構(gòu)
8.兩個單鏈表組成相加鏈表
9.刪除無序單鏈表中重復(fù)出現(xiàn)的節(jié)點
10.單鏈表刪除指定節(jié)點
11.單鏈表的選擇排序
12.一種怪異的節(jié)點刪除方式
13.有序環(huán)形單鏈表中插入新節(jié)點
14.合并兩個有序單鏈表
15.按照左右半?yún)^(qū)的方式重新組合單鏈表

三.二叉樹

1.二叉樹的序列化和反序列化
2.判斷t1樹是否包含t2樹的全部拓?fù)浣Y(jié)構(gòu)
3.判斷二叉樹是否為平衡二叉樹
4.根據(jù)后續(xù)數(shù)組重建搜索二叉樹
5.判斷一顆二叉樹是否為搜索二叉樹和完全二叉樹
6.通過有序數(shù)組生成平衡搜索二叉樹
7.通過先序和中序生成后序列數(shù)組