链表中的经典面试题
链表操作是面试中的高频考点，尤其是涉及指针移动、环检测和结构变换的问题。今天我们来深入探讨几个典型场景，重点在于边界条件的处理和代码的健壮性。
1. 链表分割
题目要求：不能改变原数据顺序，将小于 x 的节点放在前面，大于等于 x 的放在后面。
思路分析： 我们可以维护两条新链表，一条存放小于 x 的节点（bs/be），另一条存放大于等于 x 的节点（as/ae）。遍历原链表时，根据 val 值尾插到对应链表中。最后将两条链表连接起来。
这里有个细节要注意：当第一条链表为空时，直接返回第二条链表；连接完成后，务必将新链表的尾部置为 null，否则可能形成死循环。
class ListNode {
int val;
ListNode next = null;
public ListNode(int val) { this.val = val; }
}
public class Partition {
public ListNode partition(ListNode pHead, int x) {
ListNode bs = null, be = null;
ListNode as = null, ae = null;
ListNode cur = pHead;
while (cur != null) {
if (cur.val < x) {
if (bs == null) {
be = bs = cur;
} else {
be.next = cur;
be = cur;
}
} else {
if (as == null) {
ae = as = cur;
} else {
ae.next = cur;
ae = cur;
}
}
cur = cur.next;
}
// 如果小值链表为空，直接返回大值链表
if (bs == null) return as;
be.next = as; // 连接两个链表
if (as != null) {
ae.next = null; // 关键：断开尾部，防止成环
}
return bs;
}
}
2. 链表的回文结构
题目要求：判断链表是否为回文，空间复杂度需为 O(1)。
思路分析： 双指针法无法直接反向遍历单链表，因此采用'找中点 + 反转后半段'的策略。
- 使用快慢指针找到链表中间节点。
- 从中间节点开始，反转后半部分链表。
- 同时从头节点和反转后的头节点开始比较，若全部相等则为回文。
注意奇偶数节点的处理：偶数时 fast 最终为 null，奇数时为最后一个节点。比较时需小心处理相遇条件。
import java.util.Scanner;
class ListNode {
int val;
ListNode next;
public ListNode(int val) { this.val = val; }
}
public class PalindromeList {
public boolean chkPalindrome(ListNode A) {
// 1. 找到中间节点
ListNode fast = A, slow = A;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// 2. 反转后半部分
ListNode cur = slow.next;
while (cur != null) {
ListNode curN = cur.next;
cur.next = slow;
slow = cur;
cur = curN;
}
// 3. 对比前后两部分
while (A != slow) {
if (A.val != slow.val) return false;
// 偶数个节点的特殊判断
if (A.next == slow) return true;
A = A.next;
slow = slow.next;
}
return true;
}
}
3. 相交链表
题目要求：找出两个单链表相交的起始节点。
思路分析： 相交必然呈 Y 形。核心思路是对齐起点。先计算两链表长度 len1 和 len2，求出差值 len。让长链表指针先走 len 步，然后两指针同步前进，相遇点即为交点。
需注意空指针检查，以及长度差为负数时的指针交换逻辑。
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; next = null; }
}
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode pl = headA, ps = headB;
int len1 = 0, len2 = 0;
// 计算长度
while (pl != null) { len1++; pl = pl.next; }
while (ps != null) { len2++; ps = ps.next; }
pl = headA; ps = headB;
int len = len1 - len2;
// 确保 pl 指向较长链表
if (len < 0) {
pl = headB; ps = headA;
len = len2 - len1;
}
// 长链表先走 len 步
while (len != 0) {
pl = pl.next;
len--;
}
// 同步前进直到相遇
while (pl != ps) {
pl = pl.next;
ps = ps.next;
}
return pl; // 若无交点则返回 null
}
}
4. 环形链表
题目要求：判断链表中是否存在环。
思路分析： 经典的 Floyd 判圈算法（快慢指针）。慢指针每次走一步，快指针每次走两步。如果存在环，快指针终将追上慢指针；如果不存在，快指针会先到达末尾。
想象两人在环形跑道上跑步，速度快的人迟早会套圈速度慢的人。关键在于循环终止条件 fast != null && fast.next != null。
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; next = null; }
}
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) return true;
}
return false;
}
}
以上四个问题涵盖了链表操作的核心技巧。在实际编码中，指针的空值检查和边界情况往往是 Bug 的高发区，建议多画图辅助理解指针走向。
