LeetCode 160：相交链表解题思路与代码实现

步骤如下：

1. 计算长度：分别求出两个链表的长度。
2. 对齐起点：让长链表的指针先向后移动两个链表长度的差距步数。
3. 同步查找：两个迭代指针再同时移动，第一个地址相同的结点就是交点。

这样做的时间复杂度降到了 O(m + n)，依然保持 O(1) 的空间复杂度。

这里需要注意一个细节：求长度的逻辑可以封装成私有函数，避免重复代码。

private:
    size_t getLength(ListNode* list){
        ListNode* curNode = list;
        size_t length = 0;
        while(curNode){
            ++length;
            curNode = curNode->next;
        }
        return length;
    }

代码实现

暴力解法

class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        ListNode* curNode1 = headA, *curNode2 = headB;
        while(curNode1){
            while(curNode2){
                if(curNode1 == curNode2) return curNode1;
                else curNode2 = curNode2->next;
            }
            curNode1 = curNode1->next;
            curNode2 = headB;
        }
        return nullptr;
    }
};

长度差法优化版

在基础版本上，我们可以进一步精简逻辑。通过引入 longList 和 shortList 变量，减少 if-else 嵌套，使代码更清晰易读。

class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        ListNode* curNode1 = headA, *curNode2 = headB;
        
        // 分别求两个链表的长度
        size_t lengthA = getLength(headA);
        size_t lengthB = getLength(headB);
        
        // 确定长链表和短链表，以及长度差
        ListNode* longList = headA, *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;
    }
};

在实际面试或工程场景中，这种对齐思路非常通用。只要保证两个指针在'有效数据段'的起点一致，后续的比较就能线性完成。注意处理空指针的情况，上述代码已涵盖。