概述

算法中最常用的技术手段：指针、遍历、递归、while循环

指针的使用

1. 指针的作用：

• 移动节点到下一个位置
• 交换位置时，作为一个强引用的内存标记

2. 指针的好处：不需要额外的内存，起到标记的作用,而new 对象的方式，往往要创建额外的存储空间
3. 注意事项：移动指针和修改变量的区别。比如 index=index.next （移动指针，安全）， 千万不要轻易 index.next= target（修改变量），这会导致所有指向index对象next属性发生修改

比如二叉树左右节点的反转

public NodeTree invert(Node root){
    if(root ==null) return null;
    if(root.left!=null{
      invert(root.left);
      }
   if(root.right!=null{
      invert(root.right);
      }

   Node index=root.left; //设置指针
   root.left=root.right;
   root.right=index;
   return root;
}

递归的使用

运用场景：

• 树形结构的遍历
• 数组的遍历
• 链表的切分

使用：

1. 递归的第一步都是做条件判断，也就是递归的中止条件
2. 业务逻辑在前面，递归在后面，都是由上到下，由外到内的递归，比如快排
3. 业务逻辑在后面，递归在前面，都是由叶子节点到根节点，由小颗粒到大颗粒的业务过程,比如归并排序

快排中的使用

    public static void locate(int low,int high,int[] arr){
        if(low>=high) return;
        int index=low;
        int tail=high;
        while(tail>index){
            if(arr[index]>arr[index+1]){
                Util.exchange(index, index+1, arr);
                index++;
            }else if(arr[index]<arr[index+1]){
                Util.exchange(index+1, tail, arr);
                tail--;
            }
        }
        locate(low,index-1,arr);
        locate(index+1,high,arr);
    }

比如二叉树左右节点的反转

public NodeTree invert(Node root){
    if(root ==null) return null;
    if(root.left!=null{
      invert(root.left);
      }
   if(root.right!=null{
      invert(root.right);
      }

   Node index=root.left;
   root.left=root.right;
   root.right=index;
   return root;
}

递归和while循环的区别

递归是一层一层的执行的，方法的循环自我调用
while是一块一块的执行的

只有所有的left节点都遍历完了（一层一层的执行)，才执行打印，最后再执行right
root.left root.left root.left center root.right center root.right

    //中序遍历 左根右 也是顺序打印的一种方法
    public static void printTreeMid(Node root){
        if(root==null) return;
        
        printTreeMid(root.left);
        System.out.println(root.value);
        printTreeMid(root.right);
    }

单向链表的反转中，3个指针的移动是同时进行的，一块一块执行，而不是一层一层的执行

    public static Node revert(Node header){
        Node revertNode,indexNode,next;
        revertNode=header;
        indexNode=header.next;
        next=indexNode.next;
        revertNode.next=null;
        //开始反转
        while(next!=null){
            indexNode.next=revertNode;
            revertNode=indexNode;
            indexNode=next;
            next=next.next;
        }
        //反转最后一环
        indexNode.next=revertNode;
        return indexNode;
    }