给定一个链表，判断链表中是否有环。

leetcode141链接

示例

pic

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

思路1，用hashset判断。

static boolean hasCycle(ListNode head) {
        HashSet<ListNode> nodeSet = new HashSet<>();
        while (head != null){
            if(nodeSet.contains(head)){
                return true;
            }
            nodeSet.add(head);
            head = head.next;
        }
        return false;
    }

思路2：快慢指针，直到指针相遇

    public class Solution {
    public boolean hasCycle(ListNode head) {
         ListNode slow =head ;
         ListNode fast = head == null ? null :(head.next == null ? null:head.next.next);
        while (slow != null && fast != null){
            if(slow.equals(fast)){
                return true;
            }
            slow = slow.next;
            fast  =fast.next == null ? null:fast.next.next;
        }
        return false;
    }
}

复杂度O(N)

总结，链表类的思路都不是很复杂，难得是指针的写法和判断，要多加熟练

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表

leetCode206链接

示例

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

思路分析

1. 这类题我的想法是：一定要“聚焦”，就是考虑最少的元素进来，这也是数学归纳法的精髓。这里我们只考虑两个元素，当前元素head和前一个元素prev。我们归纳起来，只要把head.next 指向prev。然后后移head和prev--就可以整个反转链表
2. 要考虑链表的的断开，我们把head.next指向prev后，head和后一个元素就断开了。那么我们用一个临时变量next记录住下一个元素
   3.最后要考虑结束条件，如果临时指针next是null表示到了结尾，那么head就是新的head。

代码

ListNode reverseList(ListNode head) {
        ListNode newHead = null;
        ListNode prev = null;
        while (head != null){
            //处理断开
           ListNode next = head.next;
           //结尾处理
            if(next == null){
                newHead = head;
            }
            // 聚焦----head 指针指向前一个
           head.next = prev;
            //两个指针后移
            prev = head;
           head = next;


        }
        return newHead;
    }

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

leetcode链接

示例

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

分析

这个题很容易想到得是暴力解法和Hash解法，但是很容易得到重复的，去重的算法甚至比原算法还费力。

所以这个题用双指针左右夹逼。得到不重复的结果

1. 先对数组排序
2. 用i从头遍历数组到倒数第二位。
3. 用俩指针，j和k，j=i+1,k=len-1;
4. 如果ijk三个位置的和大于0，那么根据已经排序的特性，k--，缩小和的大小，否则j++，提高和。
5. 遇到和为0，可以退出当前i的寻找，i++继续

代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
      List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0;i < nums.length-2;i++){
            if (nums[i] > 0) {
                return list;
            }

            if(i > 0 && nums[i] ==nums[i-1]){
                continue;
            }
           int j = i + 1;
           int k = nums.length-1;
           while (j<k){
               if(nums[i] + nums[j] + nums[k] > 0){
                   k --;
               }else if( nums[i] + nums[j] + nums[k] < 0){
                   j++;
               }else{
                   List<Integer> a = new ArrayList<>();
                   a.add(nums[i]);
                   a.add((nums[j]));
                   a.add(nums[k]);
                   list.add(a);
                   while (k > j && nums[k] == nums[k - 1]) k--;
                   while (k > j && nums[j] == nums[j + 1]) j++;
                   k--;
                   j++;
               }
           }
        }
        return list;
    }
}

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

解题思想：

1. 这个是数学归纳方法，从最简单的开始算起，找到规律
2. 第n阶是n-1阶的走法 + 第n-2阶的走法之和，是一个斐波那契
3. 注意这类题是找到他的循环部分即可，不牵涉AI的算法，除了if else就是loop，抓住这道题的loop循环是关键

算法：

1. n=1,和n=2 已知，
2. n>=3 时，记住n-1用的步数和n-2用的步数，分别为f1，f2
3. 第n阶的f3就是f1+f2

    /**
     * 递推思想
     */
    private static int climbStairs(int n){
        if(n == 1) return 1;
        if(n == 2) return 2;

        int f1 = 1;
        int f2 = 2;
        int f3 =0;

        //斐波那契的缓存最近三次的结果
        for(int i = 3; i <= n  ; i++ ){
           f3 = f1 + f2;
           f1 = f2;
           f2 = f3;
        } 
        return f3;
    }

leetcode地址:https://leetcode-cn.com/problems/climbing-stairs/

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

示例

1. 暴力解法：

1. 遍历i，用右边的j去和它组成容器(为什么用右边，因为左边是i和j 指针对称调换的结果)
2. 每次算出的面积和最大值比较，取较大的。

    private static int maxArea(int[] arr,int n){
        int maxArea = 0;
        for(int i = 0; i < n ; i++){//这里注意
            for(int j =i+1;j < n;j++){
                int w = j-i;
                int h = Math.min(arr[i],arr[j]);
                int area = w*h;
                maxArea = Math.max(area,maxArea);
            }
        } 
        return maxArea;
    }

2. 左右夹逼算法---又叫左右边界向中间收敛方法，类似题目都可以使用

1. 这里使用的原理是对于指定的i，j，对应的面积S(i,j)
2. 如果对应的高度h[i] < h[j] ，那么j不用收敛，因为i是木桶原理的较小那个，j收敛也改变了木桶的最小高度。所以j收敛不可能找到更大面积的。
3. 所以i收敛，i++，并计算此时的面积，和最大面积比较
4. 然后继续比较h[i]和h[j]的高度，根据木桶原理，较小的继续收敛
5. 知道i和j相遇，就找到了最大面积；
6. 关于这个理论的证明以及动画链接：

代码如下：

 private static int maxArea2(int[] arr,int n){
        int maxArea = 0;
        System.out.print("max2");
        for(int i = 0,j=n-1; i < j ; ){

            int w = j-i;
            int h = Math.min(arr[i],arr[j]);
            maxArea = Math.max(w*h,maxArea);
            if(arr[i] <= arr[j]){
                i++;
               
            }else{
                j--; 
            }

         
            
        } 
        return maxArea;
    }