力扣爆刷第155天之TOP100五连刷41-45（下一个排列、正序数组中位数、归并排序链表）

一、31. 下一个排列

题目链接：https://leetcode.cn/problems/next-permutation/description/
思路：求下一个排列，本意就是字典序，举个例子，如果1、6、5、4、3、2的下个排列就是2、1、3、4、5、6，如果是3、2、1那么下一个排序是1、2、3，这类题目要结合图像来做，所以可以看的出来，要找的是一个转折点，从右向左寻找第一个凸起点，然后把凸起点右边的第一个大于凸起点左边的值进行交换，然后把凸起点开始到结尾的元素都翻转即可。
从下面这个图好好体会。

class Solution {public void nextPermutation(int[] nums) {if(nums.length == 1) return ;int len = nums.length, k = len-1;for(int i = len-2; i >= 0; i--) {if(nums[i] < nums[k]) {break;}k--;}if(k == 0) {reverse(nums, 0, len-1);return;}for(int i = len-1; i > k-1; i--) {if(nums[i] > nums[k-1]) {int t = nums[k-1];nums[k-1] = nums[i];nums[i] = t;reverse(nums, k, len-1);break;}}}void reverse(int[] nums, int i, int j) {while(i < j) {int t = nums[i];nums[i] = nums[j];nums[j] = t;i++;j--;}}
}

二、4. 寻找两个正序数组的中位数

题目链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/description/
思路：寻找两个正序数组的中位数，如果向时间复杂度达到log(n + m)，解法比较复杂，但是要达到o(n)还是比较简单的，只需要比较并计数即可，从头比较大小，达到总数的二分之一的位置，自然是中位数。

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int left = 0, right = 0, n = nums1.length, m = nums2.length;int i = 0, j = 0;for(int k = 0; k <= (m+n)/2; k++) {left = right;if((i < n) && (j >= m || nums1[i] < nums2[j])) {right = nums1[i++];}else {right = nums2[j++];}}return (m+n) % 2 == 0 ? (left + right) / 2.0 : right;}
}

三、232. 用栈实现队列

题目链接：https://leetcode.cn/problems/implement-queue-using-stacks/description/
思路：这也是经典题目了，用栈实现队列，需要使用两个栈，一个栈专门用来放入元素，一个栈专门用来拿出元素。
只要有元素要添加就加入第一个栈中，只要有元素要出队，都从第二个栈里出，但第二个栈如果空了，就把第一个栈内的所有元素都加入到第二个栈中，正好把先进后出，倒腾了两次，变成了先进先出了。

class MyQueue {LinkedList<Integer> stack1 = new LinkedList<>();LinkedList<Integer> stack2 = new LinkedList<>();public MyQueue() {}public void push(int x) {stack1.push(x);}public int pop() {if(stack2.isEmpty()) {while(!stack1.isEmpty()) stack2.push(stack1.pop());}return stack2.pop();}public int peek() {if(stack2.isEmpty()) {while(!stack1.isEmpty()) stack2.push(stack1.pop());}return stack2.peek();}public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}
}

四、148. 排序链表

题目链接：https://leetcode.cn/problems/sort-list/description/
思路：排序链表，使用归并排序，只需要先递归分割链表成单个节点，然后再归并单个节点即可。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode sortList(ListNode head) {return cutList(head, null);}ListNode cutList(ListNode start, ListNode end) {if(start == null) return start;if(start.next == end) {start.next = null;return start;}ListNode slow = start, fast = start;while(fast != end) {slow = slow.next;fast = fast.next;if(fast != end) {fast = fast.next;}}ListNode left = cutList(start, slow);ListNode right = cutList(slow, end);return merge(left, right);}ListNode merge(ListNode root1, ListNode root2) {ListNode root = new ListNode();ListNode p = root;while(root1 != null && root2 != null) {if(root1.val < root2.val) {p.next = root1;root1 = root1.next;}else{p.next = root2;root2 = root2.next;}p = p.next;}if(root1 != null) p.next = root1;if(root2 != null) p.next = root2;return root.next;}
}

五、69. x 的平方根

题目链接：https://leetcode.cn/problems/sqrtx/description/
思路：直接二分查找，没什么好说的。但注意不要用乘法，尽量用除非和减法。

class Solution {public int mySqrt(int x) {if(x <= 1) return x;int left = 1, right = x/2;while(left <= right) {int mid = left + (right - left) / 2;int t = x/mid;if(t == mid) return mid;else if(mid < t) left = mid+1;else right = mid-1;}return right;}
}