数组和链表
约瑟夫环问题
著名的约瑟夫问题：编号为 1-N 的 N 个士兵围坐在一起形成一个圆圈，从编号为 1 的士兵开始依次报数（1，2，3... 这样依次报数），数到 m 的 士兵会被淘汰出列，之后的士兵再从 1 开始报数。直到最后剩下一个士兵，求这个士兵的编号。
假设使用数组解决该问题，用一个长度为 N 的数组，索引表示 0～N-1 标号，要求返回最后一个士兵的编号。思路如下：
初始化剩余的士兵数 remain 为 n，重复下面操作，直到全部士兵淘汰。
初始化 count = 0，从第一个士兵开始计数，每次遍历到数值不为 -1 的元素，则 count+1，如果 count = m，说明该士兵需要被淘汰出局，则元素的值置为 -1，淘汰的数量 remain - 1，且 count 重新赋值为 0。
最后 remain = 0 时，此时的索引值便是最后剩下的士兵。
代码实现如下：
public static int josephus(int n, int m) {
int[] peoples = new int[n];
int index = -1; // 开始索引
int remain = n; // 环中剩余的人
int count = 0; // 循环数0-m
while(remain > 0) {
index++;
if(index == n)
index = 0;
// 跳过淘汰的人
if(peoples[index] == -1)
continue;
else {
count++;
if(count == m) {
peoples[index] = -1;
remain--;
count = 0;
}
}
}
return index;
}生成滑动窗口最大值数组
假设给定一个整形数组 nums 和一个大小为 k 的窗口，k 小于 nums 的长度，窗口从数组的最左边，每次滑动一个数，一直到最右边，返回每次滑动窗口中的最大值的数组。
假设输入数组为 {3, 5, -1, 3, 2, 5, 1, 6}，窗口大小为 k = 3，滑动窗口具体如下，[]中即滑动窗口的内容：
[ 3 5 -1] 3 2 5 1 6 5
3 [5 -1 3] 2 5 1 6 5
3 5 [-1 3 2] 5 1 6 3
3 5 -1 [ 3 2 5] 1 6 5
3 5 -1 3 [2 5 1] 6 5
3 5 -1 3 2 [5 1 6] 6首先是暴力解法，即每个窗口都遍历一次，找出最大值：
public static int[] maxSlidingWindow_Naive(int[] nums, int k) {
if(nums.length == 0 || k == 0)
return new int[0];
int[] result = new int[nums.length - k + 1];
for(int i = 0; i < nums.length - k + 1; i++) {
int max = nums[i];
for(int j = i; j < i + k; j++) {
max = Math.max(max, nums[j]);
}
result[i] = max;
}
return result;
}假设数组的大小为 n，窗口的大小为 k，那么滑动窗口个数就为 n-k+1，每次窗口比较获取最大数需要 k 次，所以一共要比较 k*(n-k+1) 次，时间复杂度为 O(n*k)，空间复杂度为 O(N−k+1)。
要优化时间复杂度，需要以空间换时间，使用到双向队列，不需要每次全部统计新的滑动窗口的的最大值，只需要把更大值的索引不断地保存在队列的队尾中。具体思路如下：（队列中存的是数组的索引下标）
遍历数组 nums 中的元素 nums[i]，执行以下操作。
队列的头部是最小元素，当队列不为空时，比较队列头的元素是否小于 nums[i]，若是，则移除元素，直到队列头的元素大于 nums[i]。即删除队列中较小的元素索引。
将当前元素索引 i 添加到队列头部。
移除队列尾部已经不在窗口中的元素，即如果队列尾部元素小于等于 i-k，则移除尾部元素。
若当前索引达到窗口的大小，即 i=k-1 时，开始记录窗口中的最大值，即队列尾部元素。
以数组 {3, 5, -1, 3, 2, 5, 1, 6}，窗口大小 k = 3 为例：
代码如下：
public static int[] maxSlidingWindow_Queue(int[] nums, int k) {
int n = nums.length;
if(nums.length == 0 || k == 0)
return new int[0];
int[] result = new int[n - k + 1];
// 双向队列
LinkedList<Integer> queue = new LinkedList<>();
for(int i = 0; i < n; i++) {
// 移除队列中较小元素
while(!queue.isEmpty() && nums[i] > nums[queue.getFirst()])
queue.pollFirst();
// 添加当前元素
queue.offerFirst(i);
// 移除不在窗口内的元素
if(queue.getLast() <= i - k)
queue.pollLast();
// 当前索引大于等于窗口大小时，记录最大元素
if(i - k >= -1)
result[i - k + 1] = nums[queue.getLast()];
}
return result;
}该算法最差的情况就是所有元素都进入队列，因此空间复杂度为 O(n)，而最差的情况即所有的元素都进入队列之后，又挨个出队列，加入有 n 个元素，那么就进入队列和出队列的次数就是 2n，因此时间复杂度就是 O(2n)=O(n)。
找链表的倒数 k 个元素
定义链表的节点为 ListNode，里面包含了一个属性 val，表示当前节点的值，而另一个属性 next 则表示当前节点的下一个节点的引用，定义如下：
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}如果访问链表的顺序第 k 个节点，一般是给出头结点的引用，直接循环 k--，若当前节点下一个不为 null，则向后移动一位，直到 k = 1 结束：
static ListNode findKNode(ListNode head, int k) {
ListNode node = head;
while(k > 1) {
if(node != null)
node = node.next;
k--;
}
return node;
}但是如果改为获取倒数第 k 个元素，最简单的方法是先用一个指针从头到尾走完，得到链表的长度，然后再使用一个指针又从头开始，走到 n-k+1 的位置，就是倒数第 k 个元素。这样需要遍历两次。
我们可以让两次遍历一起进行，即两个指针，一前一后，让第 1 个指针先走 k 步，然后第 2 个指针开始与第 1 个指针一起走，直到第 1 个指针走到最后的位置，此时第 2 个指针停留的位置就是倒数第 k 个元素，具体代码如下：
static ListNode findLastKNode(ListNode head, int k) {
if(head == null || k < 0)
return null;
ListNode first = head, last = head;
// 第一个指针先走 k 步
while(k > 0) {
if(first != null)
first = first.next;
k--;
}
// 两个指针一起走
while(first != null) {
first = first.next;
last = last.next;
}
return last;
}判断一个链表是否有环
有两种情况：一种是链表整体就是个环，即环形链表，一种是局部形成环。问题是给出链表的头节点，判断链表是否有环。
最直接的方法是使用 HashSet，只需要遍历时判断是否成功加入该节点，若成功加入就后移指针，若添加节点失败，说明有环，返回 true，如果遍历到 null 节点，遍历结束，没有找到相同节点，即没有环的存在，返回 false：
static boolean isContainCycle_naive(ListNode head) {
HashSet<ListNode> set = new HashSet<>();
while(head != null) {
if(!set.add(head))
return true;
head = head.next;
}
return false;
}这种方式需要借助额外空间，如果不借助 HashSet，可以使用快慢指针，让一个快指针每次走两步，慢指针每次走一步，如果两个指针能够相遇，说明快指针走过环已经从后面追上了慢指针，说明有环存在，若没有环，快指针会直接走到链表的尾部，到达 null 节点：
static boolean isContainCycle_DualPointer(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;
while(slow != fast) {
if(fast == null || fast.next == null)
return false;
slow = slow.next;
fast = fast.next.next;
}
return true;
}快慢指针的做法，没有使用额外的空间，因此空间复杂度为 O(1)，时间复杂度同样是遍历链表的时间复杂度，也就是 O(n)。
找出环入口和计算环大小
给定一个链表，返回环的入口，如果不成环，则返回 null。
如果使用 HashSet 的方法，在判断是否包含相同的节点的时候，若相同，那该节点就是环得第一个元素。但是若用快慢指针，两个指针相遇的节点不一定是环的第一个元素。
可以证明，若使用快慢指针，两个指针相遇的位置到达环入口的距离，等于从起始位置到环的入口的距离。所以，此时让快指针回到链表的头结点，慢指针在当前相遇的位置不变，两个一起移动，每次移动的步长都为 1，则它们再次相遇的位置，就是环的入口位置。动态过程如下：
代码如下：
static ListNode findCycleStartNode(ListNode head) {
if(head == null || head.next == null)
return null;
ListNode slow = head.next;
ListNode fast = head.next.next;
// 先找到相遇节点
while (slow != fast) {
if(fast == null || fast.next == null)
return null;
slow = slow.next;
fast = fast.next.next;
}
// 让一个指针回到表头，两个指针相同速度走
// 下一个相遇节点就是环的入口
fast = head;
while(fast != slow) {
fast = fast.next;
slow = slow.next;
}
return slow;
}空间复杂度为 $O(1)$，时间复杂度为 $O(n)$。
再更改一下，给定一个链表，返回环的长度，如果不成环，则返回 0。
如果快慢指针相遇，说明有环存在，所以如果相遇后，一个指针继续走，一个指针不动，当再次相遇时，两个指针正好差了一圈，其中走的指针移动的次数就是环的长度：
static int findCycleSize(ListNode head) {
if(head == null || head.next == null)
return 0;
ListNode slow = head.next;
ListNode fast = head.next.next;
while (slow != fast) {
if(fast == null || fast.next == null)
return 0;
slow = slow.next;
fast = fast.next.next;
}
int count = 0;
do {
fast = fast.next;
count++;
} while (slow != fast);
return count;
}时间复杂度为 $O(n)$，没有借助额外的空间，空间复杂度为 $O(1)$。
找两个链表的第一个公共节点
现有两个链表（没有环），但是存在着共同的部分，需要找出它们的第一个公共结点，如下图：
直接的方法是使用 HashSet，借助额外空间，先遍历添加第一个链表的所有节点，再遍历第二个链表，如果添加失败，就是第一个公共节点，时间和空间复杂度都是 $O(n + m)$ 级别。
static ListNode findFirstCommonNode_hashset(ListNode l1, ListNode l2) {
HashSet<ListNode> set = new HashSet<>();
// 先把链表1的节点添加进去
while (l1 != null) {
set.add(l1);
l1 = l1.next;
}
// 再遍历第二个链表
while(l2 != null) {
if(!set.add(l2))
return l2;
l2 = l2.next;
}
return null;
}如果不借助额外空间，可以使用双指针，可以发现从相同节点开始，后面的部分链表是相同的，所以如果从后面遍历，那么同时移动就会同时达到第一个公共节点，但是无法实现从后面开始遍历。所以要想办法从头遍历，也能同时到达公共节点。
注意到如果将两个链表各自都在最后将另一个链表拼接上，那么链表就等长了，而且相同的元素距离都是一样的，即两个指针移动相同的距离就会到达公共节点。
两个指针同时移动，当移动到 null 时，转向另一个链表的头部，开始移动，最后两个指针到达第一个公共节点移动的距离是相同的：
// 两指针步数相同，要么同时到达公共点，要么同时为 null
static ListNode findFirstCommonNode_DualPointer(ListNode l1, ListNode l2) {
ListNode p1 = l1, p2 = l2;
while (p1 != p2){
p1 = (p1 == null) ? l2 : p1.next;
p2 = (p2 == null) ? l1 : p2.next;
}
return p1;
}空间复杂度是 $O(1)$，时间复杂度为 $O(n + m)$。
翻转链表
给定一个链表，反转链表后，返回新链表的头节点。
方法是使用循环，不断把指向下一个的指针，指向前面的节点。假设链表是 1 -> 2 -> 3 -> 4，那么需要在开始时借助一个 null 节点，当 head 节点不为空的时候，先保存 head 的下一个节点，然后将 head 的 next 指向修改为指向反向，然后移动 head 指针：
直到 head 为 null 时，返回 first 即可：
static ListNode reverse_clear(ListNode head) {
if(head == null) return null;
ListNode first = null; // 反转后链表的头节点
while (head != null) {
ListNode temp = head.next; // 保存下一个节点
head.next = first; // 当前节点指向已反转部分
first = head; // 更新已反转的头节点
head = temp; // 继续处理剩余部分
}
return first;
}操作指针时尤其注意要保存下一个指针的引用，否则会出现丢失引用的情况。
合并有序链表
有两个单调递增的链表，要把它们合成一个链表，合并之后的链表需要保持递增的性质，返回头节点。
这其实就是归并排序的 merge 步骤，创建一个新链表，同时遍历两个链表，选择元素较小的加入到新链表，并移动指针，直到有一个链表遍历完，然后再把没有遍历完的那个链表中的元素直接加到新链表尾部，代码如下：
static ListNode merge(ListNode l1, ListNode l2) {
// 创建-1头节点
ListNode temp = new ListNode(-1);
ListNode res = temp;
while (l1 != null && l2 != null) {
if(l1.val < l2.val) {
temp.next = new ListNode(l1.val);
l1 = l1.next;
} else {
temp.next = new ListNode(l2.val);
l2 = l2.next;
}
// 新链表指针后移
temp = temp.next;
}
while(l1 != null) {
temp.next = new ListNode(l1.val);
l1 = l1.next;
temp = temp.next;
}
while (l2 != null) {
temp.next = new ListNode(l2.val);
l2 = l2.next;
temp = temp.next;
}
return res.next;
}时间复杂度是 $O(n + m)$，空间复杂度是 $O(1)$。
幸运数
幸运数是波兰数学家乌拉姆命名的，它采用与生成素数类似的“筛法”生成。
首先从 1 开始写出自然数 1，2，3，4，5，6，...，1 就是第一个幸运数。再从 2 开始，把所有序号能被 2 整除的项删除，变为：1 3 5 7 9 ...。
这时 3 为第2个幸运数，然后把所有能被 3 整除的序号位置的数删去。注意，是序号位置，非数本身，删除的应该是 5，11，17，...
此时 7 为第 3 个幸运数，再删除序号位置能被 7 整除的（19，39，...）。剩下的序列类似：
1， 3， 7， 9， 13， 15， 21， 25， 31， 33， 37， 43， 49， 51， 63， 67， 69， 73， 75， 79， ...
输入格式：两个正整数 m,n，空格分开（m < n < 1000*1000）。输出格式：位于 m 和 n 之间的幸运数的个数（不包含 m 和 n）。如：输入 1 20，输出 5；输入 30 69，输出 8。
由于需要不断删除元素，首先想到的数据结构是链表，可以使用现成的 LinkedList。
首先需要将除能被 2 整除之外的 1 ~ n 的数全部放到 list 中，然后从第二个元素开始取值，第一个元素是 1，没有意义。针对每个元素 num 执行以下操作：
初始化删除个数为 0，获取链表当前的长度为 size，从第一个元素开始，如果元素其序号能够被 num 整除，那么移除该元素。
按照元素的序号删除时，需要使用序号减去移除掉的元素，因为每移除一个元素，都会往前移动一位，否则会出现数组越界的情况。
删除掉之后，更新已经移除的元素个数。
最后判断 list 是否为空，若不为空，统计并返回 m 和 n 之间的元素个数。代码如下：
public static int countLuckyNum(int min, int max) {
LinkedList<Integer> list = new LinkedList<>();
// 先把能被2整除的去除
for(int i = 1; i < max; i = i + 2) {
list.add(i);
}
int index = 1;
while(index < list.size()) {
int num = list.get(index);
int numOfRemove = 0; // 偏移量
int size = list.size();
for(int i = 0; i < size; i++) {
// 序号能否被当前数整除
if((i + 1) % num == 0) {
list.remove(i - numOfRemove);
numOfRemove++;
}
}
index++;
}
int count = 0;
while(!list.isEmpty()) {
int x = list.pop();
if(x < max && x > min)
count++;
}
return count;
}但是使用 LinkedList.remove(index) 是 $O(n)$，筛选过程较慢，而且 LinkedList 由于对象包装和维护数组的指针，实际占用内存较大。可以用一个 boolean[] 数组优化：
public static int countLuckyNum2(int min, int max) {
// 处理特殊情况
if (max <= 1 || min >= max) return 0;
// 创建布尔数组，true 表示保留，false 表示删除
boolean[] isKept = new boolean[max]; // 索引 0 到 max-1 表示数字 1 到 max
// 初始时所有数字都保留
Arrays.fill(isKept, true);
// 第一步：移除所有偶数位置（序号从 1 开始，第 2、4、6...个）
// 注意数组索引与序号没对齐
for (int i = 1; i < max; i += 2) { // 注意：i 是索引，从 0 开始
isKept[i] = false; // 标记偶数位置为删除
}
// 后续筛法
int step = 1; // 对应 index，从第 2 个数字开始
while (true) {
// 找到第 step 个未删除的数字
int count = 0;
int num = -1;
for (int i = 0; i < max; i++) {
if (isKept[i]) {
count++;
if (count == step + 1) { // 第 step+1 个数字（从 0 开始计数）
num = i + 1; // num 是实际数字（索引 + 1）
break;
}
}
}
if (num == -1 || num >= max) break; // 没有足够的数字继续筛
// 用 num 标记删除
int pos = 0; // 当前未删除数字的序号
for (int i = 0; i < max; i++) {
if (isKept[i]) {
pos++;
if (pos % num == 0) { // 序号是 num 的倍数
isKept[i] = false;
}
}
}
step++;
}
// 统计 (min, max) 内的幸运数字
int count = 0;
for (int i = 0; i < max; i++) {
int num = i + 1; // 实际数字
if (isKept[i] && num > min && num < max) {
count++;
}
}
return count;
}这样当 max 很大时，该方法在执行时间上要更优。