class Solution {
public ListNode sortList(ListNode head) {
return mergeSort(head);
}
// 归并排序
private ListNode mergeSort(ListNode head){
// 如果没有结点/只有一个结点，无需排序，直接返回
if (headnull||head.nextnull) return head;
// 快慢指针找出中位点
ListNode slowp=head,fastp=head.next.next,l,r;
while (fastp!=null&&fastp.next!=null){
slowp=slowp.next;
fastp=fastp.next.next;
}
// 对右半部分进行归并排序
r=mergeSort(slowp.next);
// 链表判断结束的标志：末尾节点.next==null
slowp.next=null;
// 对左半部分进行归并排序
l=mergeSort(head);
return mergeList(l,r);
}
// 合并链表
private ListNode mergeList(ListNode l,ListNode r){
// 临时头节点
ListNode tmpHead=new ListNode(-1);
ListNode p=tmpHead;
while (l!=null&&r!=null){
if (l.val p.next=l; l=l.next; }else { p.next=r; r=r.next; } p=p.next; } p.next=l==null?r:l; return tmpHead.next; } } 快排版本。头条面试被问到了（貌似提问频率还挺高的），加了很多注释，分享给大家（交换结点版本，非伪排序只交换数值）。 class Solution { public ListNode sortList(ListNode head) { if(headnull||head.nextnull) return head; // 没有条件，创造条件。自己添加头节点，最后返回时去掉即可。 ListNode newHead=new ListNode(-1); newHead.next=head; return quickSort(newHead,null); } // 带头结点的链表快速排序 private ListNode quickSort(ListNode head,ListNode end){ if (headend||head.nextend||head.next.next==end) return head; // 将小于划分点的值存储在临时链表中 ListNode tmpHead=new ListNode(-1); // partition为划分点，p为链表指针，tp为临时链表指针 ListNode partition=head.next,p=partition,tp=tmpHead; // 将小于划分点的结点放到临时链表中 while (p.next!=end){ if (p.next.val tp.next=p.next; tp=tp.next; p.next=p.next.next; }else { p=p.next; } } // 合并临时链表和原链表，将原链表接到临时链表后面即可 tp.next=head.next; // 将临时链表插回原链表，注意是插回！（不做这一步在对右半部分处理时就断链了） head.next=tmpHead.next; quickSort(head,partition); quickSort(partition,end); // 题目要求不带头节点，返回结果时去除 return head.next; } } 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 说明：解集不能包含重复的子集。 示例: 输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/subsets 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 class Solution { public List List res.add(new ArrayList<>()); for (int i = 0; i < nums.length; i++) { int all = res.size(); for (int j = 0; j < all; j++) { List tmp = new ArrayList<>(res.get(j)); tmp.add(nums[i]); res.add(tmp); } } return res; } } 给定一个 没有重复 数字的序列，返回其所有可能的全排列。 示例: 输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/permutations 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 class Solution { public List List int[] visited = new int[nums.length]; backtrack(res, nums, new ArrayList(), visited); return res; } private void backtrack(List 《Android学习笔记总结+最新移动架构视频+大厂安卓面试真题+项目实战源码讲义》 【docs.qq.com/doc/DSkNLaERkbnFoS0ZF】 完整内容开源分享 { if (tmp.size() == nums.length) { res.add(new ArrayList<>(tmp)); return; } for (int i = 0; i < nums.length; i++) { if (visited[i] == 1) continue; visited[i] = 1; tmp.add(nums[i]); backtrack(res, nums, tmp, visited); visited[i] = 0; tmp.remove(tmp.size() - 1); } } } 给定一个二叉树的根节点 root ，返回它的 中序 遍历。 示例 1： 输入：root = [1,null,2,3] 输出：[1,3,2] 示例 2： 输入：root = [] 输出：[] 示例 3： 输入：root = [1] 输出：[1] 示例 4： 输入：root = [1,2] 输出：[2,1] 示例 5： 输入：root = [1,null,2] 输出：[1,2] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 class Solution { public List inorderTraversal(TreeNode root) { List list = new ArrayList<>(); Stack stack = new Stack<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { if (cur != null) { stack.push(cur); cur = cur.left; } else { cur = stack.pop(); list.add(cur.val); cur = cur.right; } } return list; } } } 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。 示例 1： 输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶 示例 2： 输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/climbing-stairs 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 典型的动态规划题 class Solution { // 执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户内存消耗 : // 33.2 MB, 在所有 Java 提交中击败了70.25%的用户 public int climbStairs(int n) { if(n<=2){ return n; } int i1 = 1; int i2 = 2; for(int i=3;i<=n;i++){ int temp = i1+i2; i1 = i2; i2 = temp; } return i2; } }
subsets(int[] nums) {
res = new ArrayList<>();
permute(int[] nums) {
res = new ArrayList<>();
res, int[] nums, ArrayList tmp, int[] visited)
