数据结构实战：链表经典面试题解析

2. 链表的回文结构

题目要求：判断链表是否为回文，空间复杂度需为 O(1)。

思路分析： 双指针法无法直接反向遍历单链表，因此采用'找中点 + 反转后半段'的策略。

1. 使用快慢指针找到链表中间节点。
2. 从中间节点开始，反转后半部分链表。
3. 同时从头节点和反转后的头节点开始比较，若全部相等则为回文。

注意奇偶数节点的处理：偶数时 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 的高发区，建议多画图辅助理解指针走向。