二叉树遍历
https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/87526/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/
递归解法
前序遍历
public static void preOrderRecur(TreeNode head) {
if (head == null) {
return;
}
System.out.print(head.value + " ");
preOrderRecur(head.left);
preOrderRecur(head.right);
}
作者：golandscape
链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/87526/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/
中序遍历
public static void preOrderRecur(TreeNode head) {
if (head == null) {
return;
}
preOrderRecur(head.left);
System.out.print(head.value + " ");
preOrderRecur(head.right);
}
作者：golandscape
链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/87526/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/
后序遍历
public static void postOrderRecur(TreeNode head) {
if (head == null) {
return;
}
postOrderRecur(head.left);
postOrderRecur(head.right);
System.out.print(head.value + " ");
}
作者：golandscape
链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/87526/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/
迭代解法
本质上是在模拟递归，因为在递归的过程中使用了系统栈，所以在迭代的解法中常用
Stack来模拟系统栈。
前序遍历
public static void preOrderIteration(TreeNode head) {
if (head == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(head);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.print(node.value + " ");
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
作者：golandscape
链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/87526/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/
中序遍历
public static void inOrderIteration(TreeNode head) {
if (head == null) {
return;
}
TreeNode cur = head;
Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || cur != null) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
System.out.print(node.value + " ");
if (node.right != null) {
cur = node.right;
}
}
}
作者：golandscape
链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/87526/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/
后顺遍历
public static void postOrderIteration(TreeNode head) {
if (head == null) {
return;
}
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(head);
while (!stack1.isEmpty()) {
TreeNode node = stack1.pop();
stack2.push(node);
if (node.left != null) {
stack1.push(node.left);
}
if (node.right != null) {
stack1.push(node.right);
}
}
while (!stack2.isEmpty()) {
System.out.print(stack2.pop().value + " ");
}
}
作者：golandscape
链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/87526/leetcodesuan-fa-xiu-lian-dong-hua-yan-shi-xbian-2/
层序遍历
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
List<TreeNode> queue = new LinkedList<>() {{ add(root); }}, tmp;
int res = 0;
while(!queue.isEmpty()) {
tmp = new LinkedList<>();
for(TreeNode node : queue) {
if(node.left != null) tmp.add(node.left);
if(node.right != null) tmp.add(node.right);
}
queue = tmp;
res++;
}
return res;
}
}
作者：Krahets
链接：https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/solutions/159058/mian-shi-ti-55-i-er-cha-shu-de-shen-du-xian-xu-bia/
排序算法
https://leetcode.cn/circle/article/Gwd1Z5/
https://leetcode.cn/circle/discuss/eBo9UB/#%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F
选择排序
public int[] selectionSortDouble(int[] arr) {
if (arr.length < 2) return arr;
int n = arr.length;
for (int i = 0; i < n - 1 - i; i++) { // 每轮确定两个数字，因此上界也会动态变化
int minIdx = i, maxIdx = i;
for (int j = i + 1; j < n - i; j++) {
if (arr[j] < arr[minIdx]) minIdx = j;
if(arr[j] > arr[maxIdx]) maxIdx = j;
}
if(minIdx == maxIdx) break; // 若本轮最大值等于最小值，说明未排序部分所有元素相等，无需再排序
swap(arr, i, minIdx);
if(maxIdx == i) maxIdx = minIdx; // 在交换 i 和 minIdx 时，有可能出现 i 即 maxIdx 的情况，此时需要修改 maxIdx 为 minIdx
swap(arr, n - 1 - i, maxIdx);
}
return arr;
}
作者：yukiyama
链接：https://leetcode.cn/circle/discuss/eBo9UB/
简单插入排序
// 简单插入排序：内层用 for
public int[] insertionSortUseWhile(int[] arr) {
if (arr.length < 2) return arr;
for (int i = 1; i < arr.length; i++) {
int target = arr[i], j = i - 1;
for (; j >= 0; j--) {
if(target < arr[j]) arr[j + 1] = arr[j];
else break;
}
arr[j + 1] = target;
}
return arr;
}
作者：yukiyama
链接：https://leetcode.cn/circle/discuss/eBo9UB/
双轴快排
public int[] dualPivotQuickSort(int[] arr) {
if (arr.length < 2) return arr;
dualPivotQuickSort(arr, 0, arr.length - 1); // 后两个参数是下标值
return arr;
}
/*
* 区间1 区间2 区间3
* +------------------------------------------------------------+
* | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 |
* +------------------------------------------------------------+
* ^ ^ ^
* | | |
* lower index upper
*/
private void dualPivotQuickSort(int[] arr, int left, int right) {
if(left < right) { // 排序对象是right大于left的区间（即大小大于等于2的区间）
// 令左右两端元素中较小者居左，以left为初始pivot1，right为初始pivot2
// 即arr[left]为选定的左轴值，arr[right]为选定的右轴值
if(arr[left] > arr[right]) {
swap(arr, left, right);
}
int index = left + 1; // 当前考察元素下标
int lower = left + 1; // 用于推进到pivot1最终位置的动态下标，总有[left, lower)确定在区间1中
int upper = right - 1; // 用于推进到pivot2最终位置的动态下标，总有(upper, right]确定在区间3中
// [lower, index)确定在区间2中，[index, upper]为待考察区间。
// upper以右（不含upper）的元素都是确定在区间3的元素，所以考察元素的右界是upper
while(index <= upper) {
// 若arr[index] < arr[left]，即arr[index]小于左轴值，则arr[index]位于区间1
if (arr[index] < arr[left]) {
// 交换arr[index]和arr[lower]，配合后一条lower++，保证arr[index]位于区间1
swap(arr, index, lower);
// lower++，扩展区间1，lower位置向右一位靠近pivot1的最终位置
lower++;
}
// 若arr[index] > arr[right]，即arr[index]大于右轴值，则arr[index]位于区间3
else if(arr[index] > arr[right]) {
// 先扩展区间3，使得如下while结束后upper以右（不含upper）的元素都位于区间3
// 区间3左扩不可使index == upper，否则之后的第二条upper--将导致upper为一个已经确定了区间归属的元素的位置（即index - 1）
while(arr[upper] > arr[right] && index < upper) {
upper--;
}
// 交换arr[index]和arr[upper]，配合后一条upper--，保证arr[index]位于区间3
swap(arr, index, upper);
upper--;
// 上述交换后，index上的数字已经改变，只知道此时arr[index] ≤ arr[right]，arr[index]有可能在区间1或区间2，
// 若arr[index] < arr[left]，即arr[index]小于左轴值，则arr[index]位于区间1
if(arr[index] < arr[left]) {
// 交换arr[index]和arr[lower]，配合后一条lower++，保证arr[index]位于区间1
swap(arr, index, lower);
// lower++，扩展区间1，lower位置向右一位靠近pivot1的最终位置
lower++;
}
}
index++; // 考察下一个数字
}
// while(index <= upper)结束后最后一个确定在区间1的元素的下标是lower--，
// 最后一个确定在区间3的元素下标是upper++。
lower--;
upper++;
// 双轴归位。此时的lower，upper即分别为最终pivot1(初始时为left)，最终pivot2(初始时为right)。
swap(arr, left, lower);
swap(arr, upper, right);
// 对三个子区间分别执行双轴快排
dualPivotQuickSort(arr, left, lower - 1); // 区间1
dualPivotQuickSort(arr, lower + 1, upper - 1); // 区间2
dualPivotQuickSort(arr, upper + 1, right); // 区间3
}
}
作者：yukiyama
链接：https://leetcode.cn/circle/discuss/eBo9UB/
堆排序
https://www.cnblogs.com/jiangym/p/17521231.html
链表
反转链表
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; while(cur != null){ ListNode tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; } return pre; } }
环形链表
public class Solution { public ListNode detectCycle(ListNode head) { ListNode fast = head, slow = head; while (true) { if (fast == null || fast.next == null) return null; fast = fast.next.next; slow = slow.next; if (fast == slow) break; } fast = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return fast; } } 作者：Krahets 链接：https://leetcode.cn/problems/linked-list-cycle-ii/solutions/12616/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
题解
设两指针 fast，slow 指向链表头部 head，fast 每轮走 2步，slow 每轮走 1步；
双指针第一次相遇：
第一种结果： fast 指针走过链表末端，说明链表无环，直接返回 null；
第二种结果： 当fast == slow时， 两指针在环中 第一次相遇 。
指针 位置不变 ，将fast指针重新 指向链表头部节点 ；slow和fast同时每轮向前走 1 步；
返回slow指针指向的节点。