链表
链表是面试中的高频考点，主要考察链表的遍历、节点操作、双指针技巧等。
面试题 02.01. 移除重复节点
题目描述
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
示例 1：
输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]
示例 2：
输入：[1, 1, 1, 1, 2]
输出：[1, 2]
提示：
- 链表长度在
[0, 20000]范围内。 - 链表元素在
[0, 20000]范围内。
**进阶：**如果不得使用临时缓冲区，该怎么解决？
解题思路
方法一：使用Set
遍历链表，使用Set记录出现过的节点值，如果遇到重复值则删除该节点。
方法二：双重循环（不使用额外空间）
对于每个节点，遍历其后面的所有节点，删除重复的节点。时间复杂度 O(n²)。
Java 代码实现
使用Set：
public class Solution {
public ListNode removeDuplicateNodes(ListNode head) {
if (head == null) return null;
Set<Integer> set = new HashSet<>();
set.add(head.val);
ListNode cur = head;
while (cur.next != null) {
if (set.contains(cur.next.val)) {
cur.next = cur.next.next;
} else {
set.add(cur.next.val);
cur = cur.next;
}
}
return head;
}
}
双重循环：
public class Solution {
public ListNode removeDuplicateNodes(ListNode head) {
ListNode cur = head;
while (cur != null) {
ListNode runner = cur;
while (runner.next != null) {
if (runner.next.val == cur.val) {
runner.next = runner.next.next;
} else {
runner = runner.next;
}
}
cur = cur.next;
}
return head;
}
}
面试题 02.02. 返回倒数第 k 个节点
题目描述
实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
示例：
输入： 1->2->3->4->5 和 k = 2
输出： 4
说明：
- 给定的 k 保证是有效的。
解题思路
使用快慢指针。快指针先走 k 步，然后快慢指针同时移动，当快指针到达末尾时，慢指针指向倒数第 k 个节点。
Java 代码实现
class Solution {
public int kthToLast(ListNode head, int k) {
ListNode fast = head, slow = head;
for (int i = 0; i < k; i++) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow.val;
}
}
面试题 02.03. 删除中间节点
题目描述
若链表中的某个节点，既不是链表头节点，也不是链表尾节点，则称其为该链表的"中间节点"。
假定已知链表的某一个中间节点，请实现一种算法，将该节点从链表中删除。
示例：
输入：节点 5 （位于单向链表 4->5->1->9 中）
输出：不返回任何数据，从链表中删除节点 5 ，使链表变为 4->1->9
解题思路
由于只能访问当前节点，无法获取前一个节点，所以不能直接删除当前节点。可以将下一个节点的值复制到当前节点，然后删除下一个节点。
Java 代码实现
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
面试题 02.04. 分割链表
题目描述
给你一个链表的头节点 head 和一个特定值 x，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。你不需要保留每个分区中各节点的初始相对位置。
示例 1：
输入：head = 3->5->8->5->10->2->1, x = 5
输出：3->1->2->10->5->5->8
解题思路
创建两个链表，一个存储小于 x 的节点，一个存储大于等于 x 的节点。遍历原链表，将节点分别加入对应的链表，最后将两个链表连接起来。
Java 代码实现
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode small = new ListNode(0);
ListNode large = new ListNode(0);
ListNode smallCur = small;
ListNode largeCur = large;
while (head != null) {
if (head.val < x) {
smallCur.next = head;
smallCur = smallCur.next;
} else {
largeCur.next = head;
largeCur = largeCur.next;
}
head = head.next;
}
largeCur.next = null;
smallCur.next = large.next;
return small.next;
}
}
面试题 02.05. 链表求和
题目描述
给定两个用链表表示的整数，每个节点包含一个数位。这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。
示例：
输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即 617 + 295
输出：2 -> 1 -> 9，即 912
**进阶：**假设这些数位是正向存放的，请再做一遍。
示例：
输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即 617 + 295
输出：9 -> 1 -> 2，即 912
解题思路
同时遍历两个链表，逐位相加，注意处理进位。当两个链表都遍历完后，如果还有进位，需要额外添加一个节点。
Java 代码实现
反向存放：
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int sum = carry;
if (l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}
cur.next = new ListNode(sum % 10);
cur = cur.next;
carry = sum / 10;
}
return dummy.next;
}
}
正向存放（使用栈）：
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> s1 = new Stack<>();
Stack<Integer> s2 = new Stack<>();
while (l1 != null) {
s1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
s2.push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode cur = null;
while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {
int sum = carry;
if (!s1.isEmpty()) sum += s1.pop();
if (!s2.isEmpty()) sum += s2.pop();
ListNode node = new ListNode(sum % 10);
node.next = cur;
cur = node;
carry = sum / 10;
}
return cur;
}
}
面试题 02.06. 回文链表
题目描述
编写一个函数，检查输入的链表是否是回文的。
示例 1：
输入： 1->2
输出： false
示例 2：
输入： 1->2->2->1
输出： true
**进阶：**你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解题思路
方法一：快慢指针 + 反转链表
- 使用快慢指针找到链表中点
- 反转后半部分链表
- 比较前后两部分是否相同
- 恢复链表（可选）
方法二：使用栈
遍历链表，将节点值压入栈中，再遍历链表与栈顶元素比较。
Java 代码实现
快慢指针 + 反转链表：
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) return true;
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode secondHalf = reverse(slow.next);
ListNode p1 = head, p2 = secondHalf;
boolean result = true;
while (p2 != null) {
if (p1.val != p2.val) {
result = false;
break;
}
p1 = p1.next;
p2 = p2.next;
}
slow.next = reverse(secondHalf);
return result;
}
private ListNode reverse(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
}
面试题 02.07. 链表相交
题目描述
给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null。
题目数据保证整个链式结构中不存在环。注意，函数返回结果后，链表必须保持其原始结构。
解题思路
方法一：双指针
让两个指针分别从两个链表头部出发，到达末尾后切换到另一个链表头部继续遍历。如果两个链表相交，两个指针会在交点相遇。
方法二：计算长度差
先计算两个链表的长度，让较长的链表先走长度差步，然后两个链表同时遍历。
Java 代码实现
双指针：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}
面试题 02.08. 环路检测
题目描述
给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。若环不存在，请返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
解题思路
使用快慢指针：
- 快指针每次走两步，慢指针每次走一步
- 如果相遇，说明有环
- 相遇后，将一个指针移到头部，然后两个指针每次各走一步，再次相遇的点就是环的入口
Java 代码实现
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode p = head;
while (p != slow) {
p = p.next;
slow = slow.next;
}
return p;
}
}
return null;
}
}