206.反转链表

206. 反转链表 - 力扣（LeetCode）

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

两种解法

  1. 递归

递归的函数可以看成一个已经实现了的函数 reverse ，我们通过两个节点，一个是 pre 一个 cur ，反转链表其实是交换了两个节点连接的指向，我们在递归函数中，只翻转单相的连接就行，就是先 反转cur 跟 pre ，然后把反转后的 cur 跟 next 在进行反转，这是后序的操作逻辑

    public ListNode reverseList(ListNode head) {
        return  reverse(null,head);
    }

    private ListNode reverse(ListNode pre , ListNode cur){
        if(cur == null){
            return pre;
        }
        ListNode next = cur.next;
        cur.next = pre;
        return reverse(cur, next);
    }
  1. 迭代

迭代需要维护两个指针，迭代过程中，注意操作顺序就行,先考虑最简单的情况，null -> 1 -> 2 , 分别对应三个指针 pre , cur , next ,
我们把 cur.next 先指向 pre , 然后迭代 pre 跟 cur

 public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

215. 数组中的第K个最大元素

215. 数组中的第K个最大元素 - 力扣（LeetCode）

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

由于堆的建堆与删除的平均时间是 O(logn) 不能满足 O(n) 的时间复杂度

    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(k,(x,y) -> y-x);
        for(int i = 0 ; i < nums.length ; i++){
            queue.offer(nums[i]);
        }
        int res = 0;
        while(k-- >0){
            res = queue.poll();
        }
        return res;
    }

基于快排的解决方案

quick 的基本思路，我们随机选择一个切分点，将切分点排定，保证切分元素的
左边元素都小于切分点，右边元素大于切分点,递归的排定每个子分区，最后整个数组排定

    private void quickSort(int[] nums, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int p = partition(nums, lo, hi);
        quickSort(nums, lo, p-1);
        quickSort(nums, p + 1, hi);
    }

关键在于 切分元素的选择

    private int partition(int[] nums, int lo, int hi) {
        int i = lo, j = hi + 1;
        int v = nums[i]; // 切分元素选择
        while (true) {
            while (nums[i++] < v) {
                if (i == hi) {
                    break;
                }
            }
            while (nums[j--] > v) {
                if (j == lo) {
                    break;
                }
            }
            //当 i >= j 的时候，退出循环
            if (i >= j) {
                break;
            }
            swap(nums, i, j);
        }
        swap(nums, lo, j);
        return j;
    }

回到题目中，我们对快排做个改造，

  1. 我们需要对切分逻辑做一下修改，保证倒序实现
  2. 当我们切分点 p 等于 k 的时候，我们的题目就排定了直接返回，如果 p < k 则下一步排定右侧，如果 p > k 则排定左侧

最后代码实现

    public int findKthLargest(int[] nums, int k) {
        return quickSort(nums, 0, nums.length - 1, k - 1);
    }

    private int quickSort(int[] nums, int lo, int hi, int k) {
        if (lo >= hi) {
            return nums[k];
        }
        int p = partition(nums, lo, hi);
        if (p == k) {
            return nums[p];
        } else if (p < k) {
            return quickSort(nums, p + 1, hi, k);
        } else {
            return quickSort(nums, lo, p - 1, k);
        }
    }

    private int partition(int[] nums, int lo, int hi) {
        int i = lo, j = hi + 1;
        int v = nums[i]; // 切分元素选择
        while (true) {
            while (nums[++i] > v) {
                if (i == hi) {
                    break;
                }
            }
            while (nums[--j] < v) {
                if (j == lo) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            swap(nums, i, j);
        }
        swap(nums, lo, j);
        return j;
    }

    private void swap(int[] nums, int x, int y) {
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }