一.栈
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();
}
}
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);
//他们的共同之处是建议实现类禁止添加 null 元素，否则会报空指针 NullPointerException；
//不同之处在于 add() 方法在添加失败（比如队列已满）时会报 一些运行时错误 错；而 offer() 方法即使在添加失败时也不会奔溃，只会返回 false。
//删除返回头部
//E remove();
//E poll();
//当队列为空时 remove() 方法会报 NoSuchElementException 错; 而 poll() 不会奔溃，只会返回 null。
//返回头部
//E element();
//E peek();
//当队列为空时 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()) {
//总是数量多的那个后入队列的
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.一个栈实现另外栈的排序
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.单双链表删除倒数第k个节点
//单
//类似差值
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的的确是head
//因为cur是指向head的指针.
return head;
}
//栈
//双指针
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时，慢指针就在倒数第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时，慢指针就在倒数第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）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
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;
}</code></pre></div></div><p></p><h4 id="5g8tf" name="3.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E4%B8%AD%E9%97%B4%E8%8A%82%E7%82%B9%E5%92%8Ca/b%E5%A4%84%E7%9A%84%E8%8A%82%E7%82%B9">3.删除链表的中间节点和a/b处的节点</h4><h4 id="ecc16" name="4.%E5%8F%8D%E8%BD%AC%E5%8D%95%E5%90%91%E5%92%8C%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8">4.反转单向和双向链表</h4><h4 id="8cb90" name="5.%E5%8F%8D%E8%BD%AC%E9%83%A8%E5%88%86%E5%8D%95%E5%90%91%E9%93%BE%E8%A1%A8">5.反转部分单向链表</h4><h4 id="640am" name="6.%E7%8E%AF%E5%BD%A2%E5%8D%95%E9%93%BE%E8%A1%A8%E7%BA%A6%E7%91%9F%E5%A4%AB">6.环形单链表约瑟夫</h4><h4 id="8sgv6" name="7.%E5%88%A4%E6%96%AD%E4%B8%80%E4%B8%AA%E8%A1%A8%E6%98%AF%E5%90%A6%E6%98%AF%E5%9B%9E%E6%96%87%E7%BB%93%E6%9E%84">7.判断一个表是否是回文结构</h4><h4 id="agbac" name="8.%E4%B8%A4%E4%B8%AA%E5%8D%95%E9%93%BE%E8%A1%A8%E7%BB%84%E6%88%90%E7%9B%B8%E5%8A%A0%E9%93%BE%E8%A1%A8">8.两个单链表组成相加链表</h4><h4 id="1th98" name="9.%E5%88%A0%E9%99%A4%E6%97%A0%E5%BA%8F%E5%8D%95%E9%93%BE%E8%A1%A8%E4%B8%AD%E9%87%8D%E5%A4%8D%E5%87%BA%E7%8E%B0%E7%9A%84%E8%8A%82%E7%82%B9">9.删除无序单链表中重复出现的节点</h4><h4 id="an73" name="10.%E5%8D%95%E9%93%BE%E8%A1%A8%E5%88%A0%E9%99%A4%E6%8C%87%E5%AE%9A%E8%8A%82%E7%82%B9">10.单链表删除指定节点</h4><h4 id="dvl31" name="11.%E5%8D%95%E9%93%BE%E8%A1%A8%E7%9A%84%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F">11.单链表的选择排序</h4><h4 id="5q4hv" name="12.%E4%B8%80%E7%A7%8D%E6%80%AA%E5%BC%82%E7%9A%84%E8%8A%82%E7%82%B9%E5%88%A0%E9%99%A4%E6%96%B9%E5%BC%8F">12.一种怪异的节点删除方式</h4><h4 id="1enkj" name="13.%E6%9C%89%E5%BA%8F%E7%8E%AF%E5%BD%A2%E5%8D%95%E9%93%BE%E8%A1%A8%E4%B8%AD%E6%8F%92%E5%85%A5%E6%96%B0%E8%8A%82%E7%82%B9">13.有序环形单链表中插入新节点</h4><h4 id="2o3o6" name="14.%E5%90%88%E5%B9%B6%E4%B8%A4%E4%B8%AA%E6%9C%89%E5%BA%8F%E5%8D%95%E9%93%BE%E8%A1%A8">14.合并两个有序单链表</h4><h4 id="74vtq" name="15.%E6%8C%89%E7%85%A7%E5%B7%A6%E5%8F%B3%E5%8D%8A%E5%8C%BA%E7%9A%84%E6%96%B9%E5%BC%8F%E9%87%8D%E6%96%B0%E7%BB%84%E5%90%88%E5%8D%95%E9%93%BE%E8%A1%A8">15.按照左右半区的方式重新组合单链表</h4><p></p><h3 id="98d4u" name="%E4%B8%89.%E4%BA%8C%E5%8F%89%E6%A0%91">三.二叉树</h3><p></p><h4 id="fk4fv" name="1.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%BA%8F%E5%88%97%E5%8C%96%E5%92%8C%E5%8F%8D%E5%BA%8F%E5%88%97%E5%8C%96">1.二叉树的序列化和反序列化</h4><h4 id="e5a1u" name="2.%E5%88%A4%E6%96%ADt1%E6%A0%91%E6%98%AF%E5%90%A6%E5%8C%85%E5%90%ABt2%E6%A0%91%E7%9A%84%E5%85%A8%E9%83%A8%E6%8B%93%E6%89%91%E7%BB%93%E6%9E%84">2.判断t1树是否包含t2树的全部拓扑结构</h4><h4 id="1dsiu" name="3.%E5%88%A4%E6%96%AD%E4%BA%8C%E5%8F%89%E6%A0%91%E6%98%AF%E5%90%A6%E4%B8%BA%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91">3.判断二叉树是否为平衡二叉树</h4><h4 id="fgum0" name="4.%E6%A0%B9%E6%8D%AE%E5%90%8E%E7%BB%AD%E6%95%B0%E7%BB%84%E9%87%8D%E5%BB%BA%E6%90%9C%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91">4.根据后续数组重建搜索二叉树</h4><h4 id="30o57" name="5.%E5%88%A4%E6%96%AD%E4%B8%80%E9%A2%97%E4%BA%8C%E5%8F%89%E6%A0%91%E6%98%AF%E5%90%A6%E4%B8%BA%E6%90%9C%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91%E5%92%8C%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91">5.判断一颗二叉树是否为搜索二叉树和完全二叉树</h4><h4 id="8ti5a" name="6.%E9%80%9A%E8%BF%87%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%94%9F%E6%88%90%E5%B9%B3%E8%A1%A1%E6%90%9C%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91">6.通过有序数组生成平衡搜索二叉树</h4><h4 id="3qvbh" name="7.%E9%80%9A%E8%BF%87%E5%85%88%E5%BA%8F%E5%92%8C%E4%B8%AD%E5%BA%8F%E7%94%9F%E6%88%90%E5%90%8E%E5%BA%8F%E5%88%97%E6%95%B0%E7%BB%84">7.通过先序和中序生成后序列数组</h4>
