LeetCode 160 相交链表

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

思路二：快慢指针

思路：快慢指针解法。

1. 先分别求两个链表的长度。
2. 长的链表的 curNode 指针先向后移动两个链表长度的差距步。
3. 两个迭代指针再同时移动，第一个地址相同的结点就是交点。

操作：

• ListNode* curNode1 = headA, *curNode2 = headB：curNode1和curNode2分别用于迭代遍历两个链表。
• 求链表长度的子函数。
• 分别求两个链表的长度：
  • size_t lengthA = getLength(headA)，size_t lengthB = getLength(headB);
• 比较两个链表的长度，长的链表的 curNode 指针先移动差距步。
• 再让两个 curNode 指针同时移动，第一个相同的地址就是交点。
• 时间复杂度 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;
}

代码实现

思路一：暴力解法

• 暴力解法：时间复杂度 O(n^2)，空间复杂度 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)，空间复杂度 O(1)，其中 m 和 n 分别为两个链表的长度。

// 时间复杂度为 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;
    }
};

算法代码优化

• 思路二代码优化：优化比较链表长度的逻辑，减少逻辑重复的代码。

// 优化找长链表的逻辑 时间复杂度为 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);
        // 长的链表先走差距步
        // 优化找长的链表的逻辑，假设 A 比 B 长，再加一个修正假设的逻辑
        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;
    }
};