算法相关笔记，持续更新中...

单链表

1.删除单链表中的指定节点：

public static void deleteNode(Node head,Node node){
    //删除尾节点，采用顺序查找找到尾节点的前一节点
    if（node.next == null）{
        while(head.next!=node){
          head = head.next;
        }
        head.next = null;
    }
    //要删除的节点是头结点
    else if（head==node）{
      head = null；
    }
    //要删除的节点是中间的普通节点
    else{
      Node q = node.next；
      node.data = q.data;
      node.next = q.next;
    }
}

2.单链表中删除指定数值的节点方法一：利用栈

public Node removeValue1(Node head,int num){
  Stack<Node> stack = new Stack<Node>();
  while(head !=null){
    if(head.data!=null){
      stack.push(head)；
    }
    head = head.next;
  }
  while（!stack.isEmpty()）{
    stack.peek().next = head;
    head = stack.pop();
  }
  return head;
}

3.单链表中删除指定数值的节点方法二：不利用栈

public Node removeValue2(Node head,int num){
  while(head！= null){
    if(head.data!=null){
      break；
    }
    head = head.next;
  }
  Node pre = head;
  Node cur = head;
  while(cur!=null){
    if(cur.data == num){
      pre.next = cur.next;
    }else{
      pre = cur;
    }
    cur = cur.next;
  }
  return head;
}

4.删除单链表中数值重复出现的节点

public void deleteDuplication(Node head){
  if(head == null){
    return ;
  }
  HashSet<Integer> set = new HashSet<Integer>();
  Node pre = head;
  Node cur = head.next;
  set.add(head.data)；
  while(cur!=null){
    if(set.contains(cur.data)){
      pre.next = cur.next;
    }else{
      set.add(cur.data)；
      pre = cur;
    }
    cur = cur.next;
  }
}

5.两个单链表生成相加链表

public Node addList2(Node head1,Node head2){
  Stack<Integer> stack1 = new Stack<Integer>();
  Stack<Integer> stack2 = new Stack<Integer>();
  while(head1!= null){
    stack1.push(head1.data);
    head1 = head1.next;
  }
  while(head2!= null){
    stack2.push(head2.data);
    head2 = head2.next;
  }
  int n1 = 0;//链表1的数值
  int n2 = 0;//链表2的数值
  int n  = 0;//n1+n2+ca
  int ca = 0;//进位
  
  Node node = nul;//当前节点
  Node pnode= null;//当前节点的前驱节点
  while(!stack1.isEmpty()||!stack2.isEmpty()){
    n1 = stack1.isEmpty()?0:stack1.pop();
    n2 = stack2.isEmpty()?0:stack2.pop();
    n = n1+n2+ca;
    node = new Node(n%10);
    node.next = pnode;
    pnode = node;
    ca = n/10;
  }
  
  if(ca == 1){
    pnode = node;
    node = new Node(n/10);
    node.next = pnode;
  }
  return node;
}

6.判断一个单链表是否为回文结构(1221反转1221是回文结构，1234反转4321不是回文结构)

public boolean isPalindeome1(Node head){
  if(head == null){
    retrun false;
  }
  Stack<Node> stack = new Stack<Node>();//记住这个地方不是cur.next不然最后一个节点没有压入栈
  Node cur = head;
  while(cur!=null){
    stack.push(cur);
    cur = cur.next;
  }
  while(head.next!=null){
    if(head.data != stack.pop().data){
      return false;
    }
    head = head.next;
  }
  return true;
}

7.删除单链表的倒数第k个节点

public static Node removeLastKthNode(Node head,int k){
  if(k<=0||head == null){
    return head;
  }
  Node p = head;
  for(int i = 0; i<k,i++){
    if(p.next !=null){
      p = p.next;
    }else{
      return head;
    }
  }
  Node q = head;
  while(p.next){
    p = p.next;
    q = q.next;
  }
  q.next = q.next.next;
  return head;
}

8.通过两个栈来实现一个队列
栈 先进后出；队列 先进先出

public class QueueWithStack{
  private static Stack<Object> stack1 = new Stack<Object>();
  private static Stack<Object> stack2 = new Stack<Object>();
  
  //加入队列中的元素只加入到栈1中
  public static void appendTail(Object item){
    stack.push(item);
    System.out.println(“压入栈元素”+item);
  }
  
  //删除一个元素是，检查栈2是够为空，栈2不为空则弹出栈2栈顶元素
  //栈2为空，则把栈1中的元素全部弹出，压入到栈2中，然后从栈2栈顶弹出元素
  public static void deleteHead(){
    if(!stack2.empty()){
      System.out.println(“弹出栈元素”+stack.pop());
    }else{
      if(stack.empty()){
        throw new RuntimeException("队列为空");
      }
      while(!stack1.empty()){
        Object item = stack1.pop();
        stack2.push(item);
      }
    }
  }
}

9.设计含最小函数min（）的栈，要求min，push，pop的时间复杂度都是0（1），min方法的作用是：：就能返回是栈中的最小值

public class MinStack{
  Stack<Integer> stack = new Stack<Integer>();//用来存储数据的栈
  Stack<Integer> minStack = new Stack<Integer>();//用来存储最小数据的栈
  
  //添加数据，首先是王stack栈中添加，如果最小minStack为空，或者栈顶的元素
  //比新添加的元素要大，则将新元素也要添加到辅助栈中
  public void push（int code）{
    stack.push(node);
    if(minStack.isEmpty()||((int)minStack.peek())>=node){
      minStack.push(node);
    }
  }
  
  //如果stack空，直接返回
  //如果stack不为空，得到栈顶元素，同时栈顶元素弹出
  //如果最小栈的栈顶元素与stack弹出的元素相等，那么最小站也要将其弹出
  public void pop(){
    if(stack.isEmpty()){
      return;
    }
    int node = (int)stack.peek();
    stack.pop();
    if((int)minStack.peek()==node){
      minStack.pop();
    }
  }
  
  //查看栈的最小元素
  public  int min(){
    return (int)minStack.peek();
  }

}

10.分层遍历二叉树，宽度优先遍历

public static void levelTraversal(Treenode root){
  if(root == null){
    return;
  }
  LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
  queue.push(root);
  while(!queue.isEmpty()){
    TreeNode cur = queue,removeFirst();
    System.out.print(cur.val+"");
    if(cur.left!=null){
      queue.add(cur.left);
    }
    if(cur.right!=null){
      queue.add(cur.right);
    }
  }
}

11.分层便利应用：按层打印二叉树

public ArrayList<Integer> printFromTopToBottom(TreeNode root){
  ArrayList<Integer> list = new ArrayList<Integer> ;
  Queue<TreeNode> queue = new ArrayBlockingQueue<>(100); 
  TreeNode last = root;//当前行的最后节点
  TreeNode nLast = root;//下一行的最右节点
  queue.add(root);
  while(!queue.isEmpty()){
    TreeNode out = queue.poll();
    System.out.print(out.val+"");
    list.add(out.val);
    if(out.left !=null){
      queue.add(out.left);
      nLast = out.left;
    }
    if(out.right !=null){
      queue.add(out.right);
      nLast = out.right;
    }
    if(out==last){
      System.out.print("");
      last = nLast;
    }
    
  }
  return list;
}

12.前序遍历

//（递归）
public static void preorderTraversalRec(TreeNode root){
  if(root == null){
    return;
  }
  System.out.print(root.val+" ");
  preorderTraversalRec(root.left);
  preorderTraversalRec(root.right);
}

//（迭代）
public static void preorderTraversal(TreeNode root){
  if(root == null){
    return;
  }
  Stack<TreeNode> stack = new Stack<TreeNode>();
  stack.push(root);
  while(!stack.isEmpty()){
    TreeNode cur = stack.pop();//出栈栈顶元素
    System.out.print(cur.val+" ");
    
    //关键点，要先压入右孩子，再压入左孩子，这样在出栈时会先打印左孩子再打印右孩子
    if(cur.right!=null){
      stack.push(cur.right);
    }
    if(cur.left!=null){
      stack.push(cur.left);
    }
    
  }
  
}  

13.中序遍历算法

//递归
public static void inorderTraversalRec(TreeNode root){
  if(root == null){
    return;
  }
  inorderTraversalRec(root.left);
  System.out.print(root.val+" ");
  inorderTraversalRec(root.right);
}

//迭代
public static void inorderTraversal(TreeNode root){
  if(root == null){
    return;
  }
  Stack<TreeNode> stack = new Stack<TreeNode>();
  TreeNode cur = root;
  if(cur!=null){
    while(!stack.isEmpty()||cur!=null){
      if(cur!=null){
        stack.push(cur);
        cur = cur.left;
      }else{
        cur = stack.pop();
        System.out.print(cur.val+" ");
        cur = cur.right;
      }
    }
  }
}

14.后序遍历算法（迭代）

public static void postorderTraversal(TreeNode root){
  if(root == null){
    return;
  }
  Stack<TreeNode> s = new Stack<TreeNode>();//第一个stack用于添加node和他的左右孩子
  Stack<TreeNode> output = new Stack<TreeNode>();//第二个stack用于翻转第一个stack输出
  s.push(root);
  while(!s.isEmpty()){//确保所有元素都被翻转到第二个stack
    TreeNode cur = s.pop();//把栈顶元素添加到第二个stack中
    output.push(cur);
    
    if(cur.left!=null){//把栈顶元素的左右孩子分别添加入第一个stack
      s.push(cur.left);
    }
    if(cur.right!=null){//把栈顶元素的左右孩子分别添加入第一个stack
      s.push(cur.right);
    }
  }
  
  while(!output.isEmpty()){//遍历输出第二个stack，即为后序遍历
    System.out.print(output.pop().val+" ");
  }
  
}