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

LeetCode 160：相交链表

题目描述

给定两个单链表的头节点 headA 和 headB，找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 nullptr。

提高要求：时间复杂度为 O(m + n)，空间复杂度为 O(1)，其中 m 和 n 分别为两个链表的长度。

相交链表示意图相交链表结构图相交链表路径图

思路分析

暴力解法

最直观的思路是两层循环：遍历链表 A 和链表 B，将链表 A 中的每个结点的地址都和链表 B 中的每个结点进行比较。如果地址相等，则说明找到了相交点。

具体操作如下：

使用两个指针 curNode1 和 curNode2 分别迭代遍历两个链表。
外层循环移动 curNode1，内层循环中 curNode2 从头开始遍历。
当 curNode1 == curNode2 时，代表是相交的结点，直接返回当前结点。
若内层循环结束仍未找到，curNode1 向后移动，curNode2 重置回 headB。
循环结束后若未返回，说明无交点，返回 nullptr。

该方案时间复杂度为 O(n^2)，空间复杂度为 O(1)。虽然满足空间要求，但在链表较长时效率较低。

while(curNode1){
    while(curNode2){
        if(curNode1 == curNode2) return curNode1;
        else curNode2 = curNode2->next;
    }
    curNode1 = curNode1->next;
    curNode2 = headB;
}
return nullptr;

快慢指针（长度差法）

为了优化时间复杂度，我们可以利用链表长度的特性。核心思想是让两个指针在剩余长度相同的情况下同时移动，这样它们到达交点的步数就一致了。

步骤如下：

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

这样做的时间复杂度降到了 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;
    }
};

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