Java 链表经典面试题实战：分割、回文、相交与环检测

1.2 链表的回文结构

判断单链表是否为回文结构，且空间复杂度需控制在 O(1)。双指针法无法直接反向遍历，因此采用'找中点 + 翻转后半段 + 比较'的策略。

步骤如下：

1. 找中点：使用快慢指针，fast 每次走两步，slow 每次走一步。
2. 翻转后半段：从 slow 开始，将后半部分链表原地翻转。
3. 对比：从头节点和翻转后的头节点同时向后遍历，若发现不等则返回 false。

注意奇偶节点的处理：偶数节点时，head 和 slow 相遇前会先相邻，此时应提前返回 true。

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;
    }
}

1.3 相交链表

两个链表相交后呈 Y 形。解决思路是利用长度差对齐起点。

1. 分别计算两链表长度 len1 和 len2。
2. 求出长度差 len = |len1 - len2|。
3. 让较长的链表指针先走 len 步。
4. 两指针同步前进，相遇点即为交点。

若没有交点，最终都会走到 null，此时返回 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;
        
        if (len < 0) {
            pl = headB; ps = headA;
            len = len2 - len1;
        }
        
        while (len != 0) {
            pl = pl.next;
            len--;
        }
        
        while (pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        
        return pl;
    }
}

1.4 环形链表

检测链表是否存在环，经典解法是 Floyd 判圈算法（快慢指针）。

• 慢指针一次走一步，快指针一次走两步。
• 若存在环，快指针终将追上慢指针。
• 若不存在环，快指针会率先到达末尾（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;
    }
}