LeetCode 160 题：相交链表

具体步骤：

• 定义辅助函数 getLength 计算链表长度。
• 比较 lengthA 和 lengthB，确定长链表和短链表。
• 长链表指针先行移动 gap 步。
• 随后两指针同步后移，直到相遇或到达末尾。

复杂度：

• 时间复杂度 O(m + n)
• 空间复杂度 O(1)

代码实现

暴力解法

// 暴力解法 O(n^2)
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;
    }
};

长度差解法

// 时间复杂度为 O(m + n) 的解法
class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        ListNode* curNode1 = headA, *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;
    }
};

代码优化

在实现过程中，我们可以减少逻辑重复的代码，使判断更清晰。

优化点： 将'找长链表'的逻辑封装，避免冗长的 if-else 嵌套。

// 优化找长链表的逻辑 时间复杂度为 O(m + n) 的解法
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;
    }
};

通过上述优化，代码的可读性得到提升，同时保持了算法的高效性。在实际工程中，清晰的变量命名和逻辑分层往往比单纯的算法技巧更能降低维护成本。