LeetCode 160：相交链表问题解析与代码实现

方案二：双指针（长度对齐）

为了优化性能，我们可以利用链表的结构特性。如果两个链表相交，那么从交点开始往后的节点是完全共享的。如果我们能让两个指针同时到达交点，问题就解决了。

关键在于让两个指针在剩余路径长度相等时开始同步移动。具体步骤：

1. 计算长度：先分别求出两个链表的长度。
2. 对齐起点：让较长链表的指针先走几步，直到两个指针距离交点的剩余长度一致。
3. 同步查找：两个指针同时向后移动，第一个相遇的地址即为交点。

此方法时间复杂度降为 O(m + n)，空间复杂度保持 O(1)。

// 时间复杂度为 O(m + n) 的解法
class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        ListNode* curNode1 = headA;
        ListNode* curNode2 = headB;
        
        // 分别求两个链表的长度
        size_t lengthA = getLength(headA);
        size_t lengthB = getLength(headB);
        
        // 长的链表先走差距步
        if (lengthA > lengthB) {
            size_t gap = lengthA - lengthB;
            while (gap--) curNode1 = curNode1->next;
        } else {
            size_t gap = lengthB - lengthA;
            while (gap--) curNode2 = curNode2->next;
        }
        
        // 两个链表再同时走，第一个相同的地址就是交点
        while (curNode1) {
            if (curNode1 == curNode2) return curNode1;
            else {
                curNode1 = curNode1->next;
                curNode2 = curNode2->next;
            }
        }
        return nullptr;
    }
    
private:
    size_t getLength(ListNode* list) {
        ListNode* curNode = list;
        size_t length = 0;
        while (curNode) {
            ++length;
            curNode = curNode->next;
        }
        return length;
    }
};

代码细节优化

在实际工程中，重复的条件判断可以进一步简化。比如上述代码中判断哪个链表更长后分别处理逻辑，其实可以合并为一个更通用的模式：假设 A 比 B 长，计算出差值，如果实际 B 更长则交换角色。

这样不仅减少了代码行数，也降低了维护成本。

// 优化找长链表的逻辑 时间复杂度为 O(m + n)
class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        ListNode* curNode1 = headA;
        ListNode* curNode2 = headB;
        
        // 分别求两个链表的长度
        size_t lengthA = getLength(headA);
        size_t lengthB = getLength(headB);
        
        // 统一逻辑：longList 始终指向较长的链表
        ListNode* longList = headA;
        ListNode* shortList = headB;
        size_t gap = lengthA - lengthB;
        
        if (lengthA < lengthB) {
            longList = headB;
            shortList = headA;
            gap = lengthB - lengthA;
        }
        
        // 长链表先走差距步
        while (gap--) longList = longList->next;
        
        // 两个链表再同时走，第一个相同的地址就是交点
        while (longList) {
            if (longList == shortList) return longList;
            else {
                longList = longList->next;
                shortList = shortList->next;
            }
        }
        return nullptr;
    }
    
private:
    size_t getLength(ListNode* list) {
        ListNode* curNode = list;
        size_t length = 0;
        while (curNode) {
            ++length;
            curNode = curNode->next;
        }
        return length;
    }
};

通过对比两种方案，可以看出基于长度对齐的双指针法在效率上更具优势，适合处理大规模数据场景。