链表经典算法实战：相交节点查找与回文结构判断

二、链表的回文结构

题目链接：链表的回文结构_牛客网

• 题目描述： 对于一个链表，请设计一个时间复杂度为 O(n)，额外空间复杂度为 O(1) 的算法，判断其是否为回文结构。 给定一个链表的头指针 A，请返回一个 bool 值，代表其是否为回文结构。保证链表长度小于等于 900。

（图示：链表前半部分与后半部分反转后对称）

2.1 思路解答 + 作图演示

• 算法思路：

1. 找到链表的中间节点，然后将后面的链表进行反转，再将原链表的前半部分和反转后的链表进行数值对比。 这个方法结合了寻找中间节点和链表反转的技巧。

2. 关于空间复杂度的考量： 因为有链表长度 <= 900 的前提，可以将链表转换为数组（数组大小已知），再比较。但这属于取巧的方法，如果题目没有给出关于链表长度的限制，就不能使用这个方法了，因为它违反了 O(1) 空间复杂度的要求。

3. 标准解法： 创建新的链表，将原链表的所有节点重新拷贝一份，再将链表进行反转，与原链表比较。或者直接在原链表上操作，利用快慢指针找中点，反转后半段，然后双指针比对。

2.2 验证算法

1. 验证算法思路：将链表转换为数组（受限于长度前提）

/* struct ListNode { 
   int val; 
   struct ListNode *next; 
   ListNode(int x) : val(x), next(NULL) {} 
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        // 创建数组
        int arr[900] = {0};
        // 遍历链表，将数值存放在数组中
        ListNode* pcur = A;
        int index = 0;
        while (pcur) {
            arr[index++] = pcur->val;
            pcur = pcur->next;
        }
        // 创建左右指针，双方向遍历数组比较
        int left = 0;
        int right = index - 1;
        while (left < right) {
            if (arr[left] != arr[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};

2. 验证算法思路：快慢指针 + 局部反转（符合 O(1) 空间要求）

/* struct ListNode { 
   int val; 
   struct ListNode *next; 
   ListNode(int x) : val(x), next(NULL) {} 
};*/
class PalindromeList {
public:
    // 找到中间节点
    ListNode* middleNode(struct ListNode* head) {
        // 创建快慢指针
        ListNode* fast, *slow;
        // 首先都指向头节点
        fast = head;
        slow = head;
        // 循环条件将两种情况都包含
        while (fast != NULL && fast->next != NULL) {
            // 慢指针移动一节点
            slow = slow->next;
            // 快指针移动两个节点
            fast = fast->next->next;
        }
        // 返回 slow
        return slow;
    }

    // 从中间节点开始反转链表
    ListNode* reverseList(struct ListNode* head) {
        // 创建三个指针
        ListNode* n1, *n2, *n3;
        // 链表为空
        if (head == NULL) {
            return head;
        }
        // 链表不为空
        // 首先 n1 指向空
        n1 = NULL;
        n2 = head;
        n3 = n2->next;
        while (n2) {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            // 当 n2 到达尾节点时，n3 为空，不能对空指针解引用
            if (n3) {
                n3 = n3->next;
            }
        }
        return n1;
    }

    bool chkPalindrome(ListNode* A) {
        // 找到中间节点
        ListNode* mid = middleNode(A);
        // 从中间节点开始反转
        ListNode* right = reverseList(mid);
        // 遍历原链表和反转之后的链表比较值是否相等
        ListNode* left = A;
        while (right) {
            if (right->val != left->val) {
                return false;
            }
            right = right->next;
            left = left->next;
        }
        return true;
    }
};

总结

「相交链表」的关键在于同步遍历：通过计算长度差与双指针同步移动，巧妙化解链表长度不一致的遍历难题，最终实现 O(N) 时间复杂度的高效判定。

「链表的回文结构」则需多技巧组合：寻找中间节点（快慢指针）与局部反转（三指针法）的结合，既满足了 O(1) 空间复杂度的要求，又通过对称比较精准判断回文特性。

两题共同体现了链表问题的核心解法——通过指针操作优化遍历路径，将复杂问题拆解为已知子问题，最终用简洁逻辑攻克难关。