11. 双指针（√）

10.1 剑指 Offer 18. 删除链表的节点

1. 题目说明
   
2. 代码解析
   1）方法一：遍历方法

class Solution {
    
    public ListNode deleteNode(ListNode head, int val) {
    
        ListNode result=head;
        if(result.val==val) return result.next;
        while(result!=null){
    
            if(result.next.val==val){
    
                result.next=result.next.next;
                return head;
            }
            result=result.next;
        }
        return head;
    }
}

2）方法二：递归方法

class Solution {
    
    public ListNode deleteNode(ListNode head, int val) {
    
        //递归方法
        //特殊情况
        if(head==null) return null;
        //一般情况
        if(head.val==val) return head.next;
        //递归
        head.next=deleteNode(head.next,val);
        return head;
    }
}

4. 注意事项
   1）遍历法：对链表的精细操作：需要使用一个代理人进行操作，然后还是要指向头链表。
   2）递归方法：需要处理好特殊情况和一般情况，然后就是递归表达式的书写；还有返回值。

10.2 剑指 Offer 22. 链表中倒数第k个节点

1. 题目说明
   
2. 代码详解
   1）方法一：遍历两次，第一个找到链表长度，第二次找到指定位置

class Solution {
    
    public ListNode getKthFromEnd(ListNode head, int k) {
    
        //核心思想：第一次遍历进行计数
        //第二次遍历进行输出
        int num=0;
        ListNode node=head;
        while(node!=null){
    
            num++;
            node=node.next;
        }   
        System.out.println("num="+num);
        int size=num-k+1; //相差一个1
        int num1=0;
        while(head!=null){
    
             num1++;
             if(size==num1) return head;
             head=head.next;
        }
        return head;
    }
}

2）方法二：遍历一次，使用快慢指针一步到位

class Solution {
    
    public ListNode getKthFromEnd(ListNode head, int k) {
    
        //使用快慢指针，就能够一步到位
        ListNode slow=head;
        ListNode fast=head;
        while(k-->0) fast=fast.next;
        while(fast!=null){
    
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}

3. 注意事项
   1）链表的选择：一定要使用一个代理人对链表进行操作，不然回不到头部了
   2）方法一：遍历两次，第一次计数，第二次选择。

3. 方法二：快慢指针一步到位

12. 双指针（简单）（√）

12.1 剑指 Offer 25. 合并两个排序的链表

1. 题目说明
   
2. 代码展示
   1）迭代解法

class Solution {
    
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    
        ListNode result=new ListNode();
        ListNode node=result;   //结果result的代理人
        while(l1!=null && l2!=null){
    
            if(l1.val<=l2.val){
    
                node.next=l1;
                l1=l1.next;
                node=node.next;
            }else{
    
                node.next=l2;
                l2=l2.next;
                node=node.next;
            }
        }
        //接着上面的循环，其中一方断了，把另一个的后续接上：
        if(l1==null) node.next=l2;
        if(l2==null) node.next=l1;
        return result.next;   //不是从头部开始的
    }
}

2）方法二：递归解法（优雅永不过时）

class Solution {
    
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    
    	//截止条件：特殊情况
        if(l1==null) return l2;
        if(l2==null) return l1;
        
        //一般递归条件：有返回值，那么就有赋予操作
        if(l1.val<=l2.val){
    
            l1.next=mergeTwoLists(l1.next,l2);
            return l1;
        }else{
    
            l2.next=mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
}

4. 注意事项：
   1）链表的拼接：需要一个代理人，后面还需要指向头部。
   2）递归方法：一定要想清楚递归表达式。截止表达式

12.2 剑指 Offer 52. 两个链表的第一个公共节点

1. 题目说明：指定的链表全等，而不是节点处的值相等
   
2. 代码详解

public class Solution {
    
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    
        //这里的相等是节点相同，不是节点的值相同
        //1)特殊情况
        if(headA==null || headB==null ) return null;
        //2)代理人模式
        ListNode nodeA=headA;
        ListNode nodeB=headB;
        //3)
        //会把A和B对接起来进行比较：
        while(nodeA!=nodeB){
    
            nodeA=nodeA==null?headB:nodeA.next;
            nodeB=nodeB==null?headA:nodeB.next;
        }
        return nodeA;
    }
}

3. 注意说明
   1）把两个链表给拼接起来，然后循环遍历，可以抵消距离差，一次操作
   2）浪漫的代码意义。

13. 双指针（简单）（√）

13.1 剑指 Offer 21. 调整数组顺序使奇数位于偶数

1. 题目说明
   
2. 代码展示
   1）方法一：双指针（基于快排思想）

class Solution {
    
    public int[] exchange(int[] nums) {
    
        //双指针方法：前面出现偶和后面出现奇，那就交换
        //快排的思想：一定要在while循环中，每一步都加上left<right判断条件。
        int left=0;
        int right=nums.length-1;
        while(left<right){
    
            //左边找偶数，右边找奇数
            while(left<right && nums[left]%2!=0)  left++;
            while(left<right && nums[right]%2!=1) right--;
            //找到了就进行交换
                int temp=nums[left];
                nums[left]=nums[right];
                nums[right]=temp;
        }
        return nums;
    }
}

13.2 剑指 Offer 57. 和为s的两个数字

1. 题目说明
   
2. 代码展示（双指针）

class Solution {
    
    public int[] twoSum(int[] nums, int target) {
    
        //双指针：一头一尾，大了，右边加一；小了，左边加一
        int left=0;
        int right=nums.length-1;
        while(left<right){
    
            if(nums[left]+nums[right]<target){
    
                left++;
            }else if(nums[left]+nums[right]>target){
    
                right--;
            }else{
    
                return new int[]{
    nums[left],nums[right]};
            }
        }
        return new int[2];
    }
}

13.3 剑指 Offer 58 - I. 翻转单词顺序

1. 题目说明
   
   2.代码详解
   1）方法一：使用栈操作；还有就是使用方法split，分割字符串有奇效

class Solution {
    
    public String reverseWords(String s) {
    
       //先分割为字符串数组
       String[] arr=s.split(" ");
       ArrayDeque<String> deque=new ArrayDeque<>();

       //入栈
       for(String i: arr){
    
           if(i!="") deque.push(i);
       }
       //出栈
       StringBuilder result=new StringBuilder();
       while(deque.size()>0){
    
           result.append(deque.pop());
           if(deque.size()!=0) result.append(" ");
       }
       return result.toString();
    }
}

3. 注意说明
   1）灵活使用栈；遇到需要修改字符串，一定要记得使用StringBuilder

14. 搜索与回溯算法（中等）

14.1 剑指 Offer 12. 矩阵中的路径

14.2 剑指 Offer 13. 机器人的运动范围

15. 搜索与回溯算法（中等）

15.1 剑指 Offer 34. 二叉树中和为某一值的路径

15.2 剑指 Offer 36. 二叉搜索树与双向链表

15.2 剑指 Offer 54. 二叉搜索树的第k大节点

16. 排序（简单）（√）

16.1 剑指 Offer 45. 把数组排成最小的数

1. 题目说明

2. 需要深度理解排序，把整型数组当做字符串，然后根据排序规则排序
   

3. 代码详解

class Solution {
    
    public String minNumber(int[] nums) {
    
        //重点在重写排序算法
        //1)先把整型数组转变为字符串数组
        String[] string=new String[nums.length];
        for(int i=0;i<string.length;i++){
    
            string[i]=String.valueOf(nums[i]);
        }
        //2)重写字符串数组的排序方法，使用lambda表达式，进行简写//注意compareTo的使用，如果前后顺序不变，那么就是顺序
        //易错点： 前面-后面。或者是前面与后面比较：就是升序； 后面-前面。或者是后面与前面比较：就是降序
        Arrays.sort(string,(String a,String b)->(a+b).compareTo(b+a));
        
        //把字符串数组转变为一个字符串
        StringBuilder builder=new StringBuilder();
        for(String i:string){
    
            builder.append(i);
        }
        return builder.toString();
    }
}

4. 注意事项
   1）活用排序算法
   2）常见的排序算法要能够写出来（快排，冒泡排序，堆排序）
   3）重写sort排序：要会重写排序算法，按照自己的规则【a-b负数是升序；b-a正数是逆序】

16.2 剑指 Offer 61. 扑克牌中的顺子

1. 题目说明
   
2. 代码说明
   1）需要找到零的个数，然后就是计算差值的最大值，看两者是否匹配。
   2）核心思路算是一道找规律的题目。

class Solution {
    
    public boolean isStraight(int[] nums) {
    
        //1)先排序
        Arrays.sort(nums);

        //2）看是否存在非零重复的，并记下为零的数
        int size=0;
        for(int i=1;i<5;i++){
    
            if(nums[i-1]==0){
    
                size++;
            }else{
    
                if(nums[i]==nums[i-1]) return false;
            }   
        }

        //3)计算非零最大值-最小值
        int sum=nums[4]-nums[size];
        
        //4)如果两者小于等于4，那么就正确
        if(sum<=4) return true;
        return false;
    }
}

17. 排序（简单）（√）

17.1 剑指 Offer 40. 最小的k个数 **经典题目，一定要多看

1. 题目说明 2. 代码分析（使用快排的改进，时间复杂度为O(n）

class Solution {
    
    public int[] smallestK(int[] arr, int k) {
    
        //快排的改进
        method(arr,0,arr.length-1,k);
        return Arrays.copyOfRange(arr,0,k);
    }
    public static void method (int[] arr,int first,int end,int k){
    
        
        int left=first;
        int right=end;
        //1)特殊情况
        if(left>=end) return;
        
        //2)一般操作
        int target=arr[left];
        while(left<right){
    
            //1)寻找左右两边交换值
            while(left<right && arr[right]>target) right--;
            while(left<right && arr[left]<=target) left++;
            //进行数据交换(arr[left],arr[right])
            int temp=arr[left];
            arr[left]=arr[right];
            arr[right]=temp;
        }
        //初始和中间交换（arr[first],arr[left]）
        arr[first]=arr[left];
        arr[left]=target;

        //3)递归操作
        if(left<k){
    
            method(arr,left+1,end,k);
        }else if(left>k){
    
            method(arr,first,left-1,k);
        }else{
    
            return;
        }
    }
}

3. 注意事项
   1）本题有：大顶堆，快排和快排的改进算法
   2）大顶堆需要注意数据的存入和排除，采用队列的方法，还有重写大顶堆的方法（默认为小顶堆，出来的数最小）
   3）快排的思想一定要掌握，递归的思想。（基于快排的改进，只是变了一下方向而已）

17.2 剑指 Offer 41. 数据流中的中位数（困难题目，没做）

18. 搜索与回溯算法（中等）

18.1 剑指 Offer 55 - I. 二叉树的深度

18.2 剑指 Offer 55 - II. 平衡二叉树

19. 搜索与回溯算法（中等）

19.1 剑指 Offer 64. 求1+2+…+n

19.2 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

19.2 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

19.3 剑指 Offer 68 - II. 二叉树的最近公共祖先

20. 分治算法（中等）

20.1 剑指 Offer 07. 重建二叉树

20.2 剑指 Offer 16. 数值的整数次方

20.3 剑指 Offer 33. 二叉搜索树的后序遍历序列