专栏原创出处：github-源笔记文件 (opens new window) ，github-源码 (opens new window)，欢迎 Star，转载请附上原文出处链接和本声明。
# 1. 解题思路
拿到题目，开始考虑暴力解法，借助暴力方法我们可以在过程上继续优化，循序渐进的优化复杂度。
寻找关键字
提取题目关键字，比如给定一个「二叉树」与给定一个「完美二叉树」解题思路可能完全不一样。案例 力扣 116 (opens new window) / 力扣 117 (opens new window)
画图分析
许多问题依靠大脑不能很好的立马想出方案，尤其涉及链表相关问题。推荐采用画图模式分析解题过程，这样在转换代码时更为流畅。
注意边界、重复、溢出问题
一定考虑数据边界问题，尤其是
>= > < <= null 空头、空尾...之类的问题，很多 BUG 都是因为边界处理不周全导致的。注意递归重复计算问题，返回值溢出问题。优先考虑原地算法
先不考虑借助外部数据结构尝试原地算法 (opens new window)，当然如果本身数据不允许修改本身时只能借助外部数据临时存储。
借助外部数据结构
分析题目过程中的一些特点，是否执行替换操作、当前操作是否依赖历史数据、过程数据的流向。 一般情况，如果涉及替换、反转类操作考虑指针（双指针）。如果涉及历史数据时考虑指针记录是否满足，不满足时使用数据结构。比如先进后出、先进先出、KV 映射哈希表。 在使用数据结构时，尽量减少空间复杂度。比如我们的一个数组，可以记录一个下标，前半部分用于删除后半部分用于修改。
# 2. 双指针技巧
# 2.1 对撞指针-两个指针从两端向中间迭代
一个指针从始端开始，而另一个指针从末端开始。
关键词：反转字符串、排序数组、原地算法、首尾替换
// 案例：将输入的字符串反转过来
// 输入：["h","e","l","l","o"] 输出：["o","l","l","e","h"]
class Solution {
public void reverseString(char[] s) {
int min = 0; // 开始位置
int max = s.length - 1; // 末尾位置
while (min < max) { // 向中间迭代
char minVal = s[min];
s[min++] = s[max];
s[max--] = minVal;
}
}
}
# 2.2 窗口指针-两个指针保持一定距离
使用两个指针，两个指针保持一定的窗口距离进行迭代。
关键词：删除倒数第 N 个问题
// 案例：删除链表的倒数第 N 个节点
// 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode sentinel = new ListNode(0); // 哨兵节点,避免头节点 null 问题
sentinel.next = head;
ListNode first = sentinel; // 第一个指针
ListNode second = sentinel;// 第二个指针
// 第二个指针先前进 n 步
for (int i = 0; i < n; i++) second = second.next;
while (second.next != null) { // 同步向后迭代，第二个指针到末尾即寻找结束
first = first.next;
second = second.next;
}
first.next = first.next.next; // 第一个指针指向的节点，即为移除节点
return sentinel.next;
}
# 2.3 快慢指针
使用两个指针，一个快指针和一个慢指针。指针的移动策略取决于条件本身。
关键词：原地删除、寻找环形链表环形入口点（环形链表 II）、两个单链表相交的起始节点（相交链表）
// 案例：移除元素
// 给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
public int removeElement(int[] nums, int val) {
int i = 0; // 快指针
int k = nums.length - 1; // 慢指针
while (i <= k) {
if (nums[i] == val) { // 不相等时将值交换到末尾
nums[i] = nums[k--];
} else {
i++;
}
}
return k + 1;
}
// 案例：判断单链表是否是环形链表（链表中有一个环，其尾部连接到前面的节点。）
// 双指针,每次移动慢指针一步，而移动快指针两步。每一次迭代，快速指针将额外移动一步。
// 如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环 N 周，并赶上慢指针。
public boolean hasCycle(ListNode head) {
ListNode slow = head; // 慢指针
ListNode fast = slow; // 快指针
do {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
} while (fast != slow);
return true;
}
# 3. 哨兵节点（哑节点、伪节点）-避免空问题
我们在移除单链表的元素时，如果移除的是中间的元素，直接使用「curr」「prev」两个指针来处理。 但是如果移除的是头部节点时，「prev」为空。使用了哨兵节点后我们避免对 「null」 处理。
哨兵节点广泛应用于树和链表中，如伪头、伪尾、标记等，它们是纯功能的，通常不保存任何数据，其主要目的是使链表标准化，如使链表永不为空、永不无头、简化插入和删除。
// 案例：删除链表中等于给定值 val 的所有节点。
public ListNode removeElements1(ListNode head, int val) {
ListNode sentinel = new ListNode(0); // 哨兵节点
sentinel.next = head; // 本身的头节点挂在到哨兵节点
ListNode curr = head; // 当前节点
ListNode prev = sentinel; // 当前节点的上一个节点，默认为哨兵节点
while (curr != null) {
if (curr.val == val) { // 相等，移除当前节点 curr
// 上一个节点直接指向下下一个节点。如果不用哨兵节点需要判断 null 重置头节点
prev.next = curr.next;
} else prev = curr; // 不能移除时，当前节点更新为上一个节点
curr = curr.next; // 继续寻找下一个节点
}
return sentinel.next; // 移除哨兵节点返回真实的头节点
}
# 4. 求和（进位、最终进位）
求和问题需要考虑进位问题，最终结果考虑是否加 1 。
运算，通常我们会考虑进位问题，有时也会忽略了处理最终进位时错误的输出 00，百位的 1 可能丢失。
// 案例：两数相加 https://leetcode-cn.com/problems/add-two-numbers/
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
输入：(9 -> 9 -> 9) + (1)
输出：1 -> 0 -> 0 -> 0
原因：999 + 1 = 1000
# 参考
更多相关专栏内容汇总：
