2025高频面试算法总结篇【链表堆栈队列】

---

直接刷题链接直达

1. 反转链表

• 206. 反转链表

2. 环形链表

• 141. 环形链表
• 142. 环形链表 II

3. 判断一个序列是否为合理的出栈顺序

• 946. 验证栈序列

4. 最长有效括号

• 32. 最长有效括号

5. 旋转链表

• 61. 旋转链表

6. 删除链表 M 个节点之后的 N 个节点

• 删除链表 M 个节点之后的 N 个节点

7. 复杂链表的复制

• 138. 复制带随机指针的链表

8. 约瑟夫环问题

• 面试题62. 圆圈中最后剩下的数字

9. 滑动窗口最大值

• 239. 滑动窗口最大值

---

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseList(ListNode head) {if (head == null || head.next == null) return head;ListNode pre = null;ListNode curr = head;ListNode next = null;while (curr != null) {next = curr.next;curr.next = pre;pre = curr;curr = next;}return pre;}
}

---

环形链表

解法：
(1)采用快慢指针去判断链表是否有环，有环快慢指针一定会相遇。
(2)有环，找到这个环入点，先快慢指针，判断环，然后快指针赋值head，快慢指针，保持相同的速度1，遍历，直到相等，这个节点就是入点。

题目： 给你一个链表的头节点 head ，判断链表中是否有环。

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {if (head == null || head.next == null) {return false;}ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {return true;}}return false;}
}

---

题目：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {// 判断有没有环if (head == null || head.next == null) return null;ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {break;}}// 有环if (fast != null && fast.next != null) {fast = head;while (fast != slow) {fast = fast.next;slow = slow.next;}return fast;}// 没环return null;}
}

判断一个序列是否为合理的出栈顺序

题目：给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。

class Solution {public boolean validateStackSequences(int[] pushed, int[] popped) {Stack<Integer> stack = new Stack<>();int k = 0;for (int num: pushed) {stack.push(num);while (!stack.isEmpty() && stack.peek() == popped[k]) {stack.pop();k++;}}return stack.isEmpty();}
}

---

最长有效括号

题目： 给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

思路:

• 用栈存储括号索引，帮助找到匹配的子串长度。
• 遍历字符串：
  • 遇到 ( 入栈。
  • 遇到 ) 出栈，计算最长有效长度。
• 额外维护 -1 作为基准索引，避免匹配失败时无法计算长度。

class Solution {public int longestValidParentheses(String s) {// 栈初始化，存储索引Stack<Integer> stack = new Stack<>();stack.push(-1); // 这个 -1 是为了处理从第一个字符开始的有效括号情况int maxLen = 0; // 用于记录最长有效括号的长度for (int i = 0; i < s.length(); i++) {if (s.charAt(i) == '(') {stack.push(i);}else {stack.pop();if (stack.isEmpty()) {stack.push(i);}else {maxLen = Math.max(maxLen, i - stack.peek());}}}return maxLen;}
}

---

旋转链表

题目： 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

class Solution {public ListNode rotateRight(ListNode head, int k) {if (head == null || head.next == null || k == 0) return head;// 计算链表长度int n = 0;ListNode curr = head;while (curr != null) {curr = curr.next;n++;}k = n - k % n;if (k == n) {return head;}ListNode pre = head;for (int i = 1; i < k; i++) {pre = pre.next;}ListNode newHead = pre.next;pre.next = null;curr = newHead;while (curr.next != null) {curr = curr.next;}curr.next = head;return newHead;}
}

---

题目描述： 给定一个单链表 head 和两个整数 M 和 N，你需要按照如下规则修改链表：

• 保留 链表的前 M 个节点。
• 删除 接下来的 N 个节点。
• 重复 上述过程，直到遍历完整个链表。

class ListNode {int val;ListNode next;ListNode(int x) { val = x; }
}public class Solution {public ListNode deleteNodes(ListNode head, int M, int N) {ListNode curr = head;  // 当前遍历的节点while (curr != null) {// 1. 保留 M 个节点for (int i = 1; i < M && curr != null; i++) {curr = curr.next;}if (curr == null) break;  // 已到链表末尾// 2. 删除 N 个节点ListNode temp = curr.next;  // temp 用于删除后续的 N 个节点for (int i = 0; i < N && temp != null; i++) {temp = temp.next;}// 3. 连接 M 个节点之后的剩余部分curr.next = temp;curr = temp; // 继续遍历}return head;}public static void main(String[] args) {Solution solution = new Solution();// 构造链表 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10ListNode head = new ListNode(1);ListNode curr = head;for (int i = 2; i <= 10; i++) {curr.next = new ListNode(i);curr = curr.next;}int M = 2, N = 3;  // 示例：保留2个，删除3个ListNode newHead = solution.deleteNodes(head, M, N);// 打印结果while (newHead != null) {System.out.print(newHead.val + " -> ");newHead = newHead.next;}System.out.println("NULL");}
}

---

复杂链表的复制

题目： 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

/*
// Definition for a Node.
class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}
}
*/class Solution {public Node copyRandomList(Node head) {if (head == null) {return null;}Map<Node, Node> map = new HashMap<>();Node cur = head;while (cur != null) {map.put(cur, new Node(cur.val));cur = cur.next;}cur = head;while (cur != null) {map.get(cur).next = map.get(cur.next);map.get(cur).random = map.get(cur.random);cur = cur.next;}return map.get(head);}}

---

约瑟夫环问题

题目： 社团共有 num 位成员参与破冰游戏，编号为 0 ~ num-1。成员们按照编号顺序围绕圆桌而坐。社长抽取一个数字 target，从 0 号成员起开始计数，排在第 target 位的成员离开圆桌，且成员离开后从下一个成员开始计数。请返回游戏结束时最后一位成员的编号。

class Solution {public int iceBreakingGame(int num, int target) {List<Integer> list = new ArrayList<>();for (int i = 0; i < num; i++) {list.add(i);}int idx = 0;while (num > 1) {idx = (idx + target - 1) % num;list.remove(idx);num--;}return list.get(0);}
}

---

滑动窗口最大值

题目： 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

import java.util.Deque;
import java.util.LinkedList;class Solution {public int[] maxSlidingWindow(int[] nums, int k) {// 单调队列（存储索引，保持递减）Deque<Integer> dq = new LinkedList<>();int[] ans = new int[nums.length - k + 1];for (int i = 0; i < nums.length; i++) {// 1. 维护单调递减队列while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {dq.pollLast();}// 2. 移除超出窗口的元素（队列头部）while (!dq.isEmpty() && dq.peekFirst() <= i - k) {dq.pollFirst();}// 3. 添加当前元素索引dq.addLast(i);// 4. 只有当窗口形成（i >= k - 1）时，才开始记录答案if (i >= k - 1) {ans[i - k + 1] = nums[dq.peekFirst()];}}return ans;}}

---