数据结构：相交链表、随机链表复制及链表回文问题解析

一、相交链表问题

问题描述

给定两个单链表，判断它们是否相交，若相交则返回相交的节点。（注意：判断依据是节点地址是否相同，而非节点值，因为节点值可能存在重复。）

解题思路分析

思路一：暴力遍历法

• 方法：遍历链表 A，对于 A 中的每一个节点，遍历整个链表 B，检查是否存在地址相同的节点。
• 时间复杂度：O(M*N)（若两链表长度分别为 M 和 N）
• 空间复杂度：O(1)
• 缺点：效率低，不适用于长链表。

思路二：双指针对齐法（最优解）

• 方法：
  1. 分别遍历两个链表，计算各自长度。
  2. 求出两链表长度差 gap。
  3. 让较长的链表的指针先移动 gap 步。
  4. 然后两个指针同时移动，逐个比较节点地址，第一个相同的节点即为交点。
• 时间复杂度：O(M + N)
• 空间复杂度：O(1)
• 优点：高效，适用于任意长度的链表。

思路 2 的时间复杂度更低，所以我们选择思路 2

具体代码如下：

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* curA = headA, *curB = headB;
    int lenA = 1, lenB = 1;
    while (curA->next) { curA = curA->next; lenA++; }
    while (curB->next) { curB = curB->next; lenB++; }
    int gap = abs(lenA - lenB);
    struct ListNode* longList = headA;
    struct ListNode* shortList = headB;
     (lenA < lenB) { longList = headB; shortList = headA; }
     (gap--) { longList = longList->next; }
     (longList) {
         (longList == shortList)  longList;
        longList = longList->next;
        shortList = shortList->next;
    }
     ;
}