仅保留关键代码
- Recursive
class BinaryTreeInorderTraversal {
List<Integer> m0(TreeNode root) {
List<Integer> ret = new ArrayList<>();
ret.addAll(binaryTreeInorderTraversal(root.left));
ret.add(root.val);
ret.addAll(binaryTreeInorderTraversal(root.right));
return ret;
}
}- Iterative
class BinaryTreeInorderTraversal {
List<Integer> m0(TreeNode root) {
List<Integer> ret = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
for (TreeNode node = root; node != null && !stack.isEmpty(); ) {
while (node != null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
ret.add(node.val);
node = node.right;
}
return ret;
}
}使用散列来存储已遍历过的数（值-索引）。 当前数通过查表来获取配对。
class TwoSum() {
int[] m0(int[] nums, int target) {
Map<Integer, Integer> mm = new HashMap<>();
for (int i = 0, N = nums.length; i < N; i++) {
if (mm.containsKey(target - nums[i])) {
return new int[]{mm.get(target - nums[i]), i};
} else {
mm.put(nums[i], i);
}
}
return null;
}
}- 排序数组
- 取数做锚点，然后 [lo, hi] 两个指针向中间扫描
class ThreeSum {
List<List<Integer>> m0(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ret = new ArrayList<>();
for (int i = 0; i < N - 2; i++) {
if (i == 0 || nums[i] != nums[i - 1]) { // 前面相同的数已经处理过，该重复的数就不处理了
int sum = -nums[i];
int lo = i + 1;
int hi = N - 1;
while (lo < hi) {
if (sum == nums[lo] + nums[hi]) {
ret.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
while (lo < hi && nums[lo] == nums[lo + 1]) { // 跳过重复数
lo++;
}
while (lo < hi && nums[hi] == nums[hi - 1]) { // 跳过重复数
hi--;
}
} else if (sum > nums[lo] + nums[hi]) {
lo++;
} else {
hi--;
}
}
}
}
return ret;
}
}注意进位
class AddTwoNumbers {
ListNode m0(ListNode l1, ListNode l2) {
ListNode sentry = new ListNode(0);
ListNode node = sentry;
int c = 0;
while (l1 != null || l2 != null) {
if (l1 != null) {
c += l1.val;
l1 = l1.next;
}
if (l2 != null) {
c += l2.val;
l2 = l2.next;
}
node.next = new ListNode(c % 10);
node = node.next;
c /= 10;
}
if (c != 0) {
node.next = new ListNode(c);
}
return sentry.next;
}
}通过快慢指针将间距拉开N
class RemoveNthNodeFromEndOfList {
ListNode m0(ListNode head, int n) {
ListNode sentry = new ListNode(0, head);
ListNode slow = sentry;
ListNode fast = sentry;
for (int i = 0; i <= n; i++) {
fast = fast.next;
}
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return sentry.next;
}
}- Recursive
class MergeTwoSortedLists {
ListNode m0(ListNodo l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else {
if (l1.val < l2.val) {
l1.next = m0(l1.next, l2);
return l1;
} else {
l2.next = m0(l1, l2.next);
return l2;
}
}
}
}- Iterative
class MergeTwoSortedLists {
ListNode m0(ListNode l1, ListNode l2) {
ListNode sentry = new ListNode(0);
ListNode x = sentry;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
x.next = l1;
l1 = l1.next;
} else {
x.next = l2;
l2 = l2.next;
}
x = x.next;
}
if (l1 != null) {
x.next = l1;
} else {
x.next = l2;
}
return sentry.next;
}
}将数据存入优先级队列
从优先级队列获取的结点就是最小结点，拼接到返回链表
将剩下的部分再次存入优先级队列
直到优先级队列为空
class MergeKSortedLists {
ListNode m0(ListNode[] lists) {
int N = lists.length;
if (N == 0) {
return null;
}
if (N == 1) {
return lists[0];
}
PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
for (ListNode node : lists) {
pq.offer(node);
}
ListNode sentry = new ListNode(0);
ListNode ptr = sentry;
while (!pq.isEmpty()) {
ptr.next = pq.poll();
ptr = ptr.next;
if (ptr.next != null) {
pq.offer(ptr.next);
}
}
return sentry.next;
}
}- Recursive
class SwapNodesInPairs {
ListNode m0(ListNode head) {
if (head == null || head.next == null) {
return head;
} else {
ListNode r = m0(head.next.next);
ListNode s = head.next;
head.next = r;
s.next = head;
return s;
}
}
}- Iterative
class SwapNodesInPairs {
ListNode m0(ListNode head) {
if (head == null || head.next == null) {
return head;
} else {
ListNode sentry = new ListNode(0, head);
ListNode ptr = sentry;
while (head != null && head.next != null) {
ListNode cur = head;
ptr.next = head.next;
cur.next = head.next.next;
ptr.next.next = cur;
ptr = cur;
head = ptr.next;
}
return sentry.next;
}
}
}计算链表长度
将通过快慢指针将链表分成两部分
class RotateList {
ListNode m0(ListNode head) {
if(head!=null && head.next!=null) {
ListNode fast = head;
ListNode slow = head;
int size = 0;
while (fast.next != null) {
size++;
fast = fast.next;
}
size++;
for (int i = size - k % size - 1; i > 0; i--) {
slow = slow.next;
}
fast.next = head;
head = slow.next;
slow.next = true;
}
return head;
}
}如果发现相邻的元素相同，则依次跳过这些结点
- Recursive
class RemoveDuplicatesFromSortedListII {
ListNode m0(ListNode head) {
if (head == null || head.next == null) {
return head;
} else {
if (head.val != head.next.val) {
head.next = m0(head.next);
return head;
} else {
while (head.next != null && head.val == head.next.val) {
head = head.next;
}
return m0(head.next);
}
}
}
}- Iterative
class RemoveDuplicatesFromSortedListII {
ListNode m0(ListNode head) {
if (head == null || head.next == null) {
return head;
} else {
ListNode sentry = new ListNode(0, head);
ListNode ptr = sentry;
ListNode x = head;
while (x != null) {
while (x.next != null && x.val == x.next.val) {
x = x.next;
}
if (ptr.next = x) {
ptr = ptr.next;
} else {
ptr.next = x.next;
}
x = x.next;
}
ptr.next = null;
return sentry.next;
}
}
}快慢指针
快指针遍历所有元素，慢指针拼接所有不重复元素
class RemoveDuplicatesFromSortedList {
ListNode m0(ListNode head) {
if (head != null && head.next != null) {
ListNode ptr = head;
for (ListNode x = head.next; x != null; x = x.next) {
if (ptr.val != x.val) {
ptr.next = x;
ptr = ptr.next;
}
}
ptr.next = null;
}
return head;
}
}两个链表表示前后两段
两个指针表示链表的末尾
class Partition {
ListNode mo(ListNode head, int x) {
ListNode rest = new ListNode(0);
ListNode next = rest;
ListNode temp = new ListNode(0);
ListNode prev = temp;
while (head != null) {
if (head.val < x) {
prev.next = head;
prev = pre.next;
} else {
next.next = head;
next = next.next;
}
head = head.next;
}
next.next = null;
prev.next = rest.next;
return temp.next;
}
}保存前一段链表
反转 [m, n] 链表（注意结尾处 n = length）
class ReverseLinkedListII {
ListNode m0(ListNode head, int m, int n) {
if (head == null || head.next == null || m == n) {
return head;
}
ListNode ret = new ListNode(0, head);
ListNode prev = ret;
for (int i = 1; i < m; i++) {
prev = prev.next;
}
ListNode next = prev.next;
ListNode node;
for (int i = m; i < n; i++) {
node = next.next;
next.next = node.next;
node.next = prev.next;
prev.next = node;
}
return ret.next;
}
}通过拼接两个链表讲其对其，然后两两比较
class IntersectionOfTwoLinkedList {
ListNode m0(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode x = headA;
ListNode y = headB;
while (x != y) {
x = (x == null) ? headB : x.next;
y = (y == null) ? headA : y.next;
}
return x;
}
}- Iterative
class RemoveLinkedListElements {
ListNode m0(ListNode head, int val) {
ListNode sentry = new ListNode(0, head);
ListNode prev = sentry;
ListNode node = prev.next;
while (node != null) {
if (node.val == val) {
prev.next = node.next;
} else {
prev = node;
}
node = prev.next;
}
return sentry.next;
}
}- Recursive
class RemoveLinkedListElements {
ListNode m0(ListNode head, int val) {
if (head == null) {
return null;
}
if (head.val == val) {
return m0(head.next, val);
}
head.next = m0(head.next, val);
return head;
}
}通过快慢指针将链表分成两部分 在遍历的过程中，将前部分的链表反转
class PalindromeLinkedList {
boolean m0(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode s = head;
ListNode f = head;
ListNode t;
ListNode x = null;
while (f != null && f.next != null) {
t = s;
s = s.next;
f = f.next.next;
t.next = x; // reverse
x = t;
}
if (f != null) { // ignore odd center node
s = s.next;
}
for (; s != null; s = s.next, x = x.next) {
if (s.val != x.val) {
return false;
}
}
return true;
}
}合并当前结点与下一个结点，将其看做一个结点 其中数据是当前结点的下一个结点的数据 指针指向当前结点的下下个结点
class DeleteNodeInALinkedList {
void m0(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}快慢指针
class MiddleOfTheLinkedList {
ListNode m0(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode slow = head;
ListNode fast = head.next.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow.next;
}
}class ConvertBinaryNumberInALinkedListToInteger {
int m0(ListNode head) {
int ret = 0;
while (head != null) {
ret = ret * 2 + haed.val;
head = head.next;
}
return ret;
}
}