关关的刷题日记75 – Leetcode 160. Intersection of Two Linked Lists- 专知

关关的刷题日记75 – Leetcode 160. Intersection of Two Linked Lists

点击上方“专知”，关注获取专业AI知识”

关关的刷题日记75 – Leetcode 160. Intersection of Two Linked Lists

题目

思路

思路：题目让求两个单链表的起始交叉点，但是给出了很多限制。要求不开辟额外空间，时间复杂度是O(n)，这样我们就不能双重循环遍历两个链表来做。题目要求函数结束之后两个链表不能发生改变，这样我们就不能转置链表来做。想到直接从前往后遍历两个链表，就面临着不能同时到达交叉点的问题，因为两个链表有可能不一样长。如果两个链表一样长就好办了，第一个相同的当前节点就是交叉点。分别遍历两个链表求出各自长度len1, len2. 较短的链表从头开始遍历，较长的链表从|len2-len1|+1节点开始遍历，这时候两个链表就“一样长”了，第一个相同的当前节点即为所求。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int count1=0, count2=0;
        ListNode *p1, *p2;
        p1=headA;
        p2=headB;
        while(p1!=nullptr)
        {
            count1++;
            p1=p1->next;
        }
        while(p2!=nullptr)
        {
            count2++;
            p2=p2->next;
        }
        if(count1 < count2)
        {
            for(int i=1; i<=count2-count1; i++)
                headB=headB->next;
        }
        else
        {
            for(int i=1; i<=count1-count2; i++)
                headA=headA->next;
        }
        while(headA!=nullptr && headB!=nullptr)
        {
            if(headA==headB)
                return headA;
            headA=headA->next;
            headB=headB->next;
        }
        return nullptr;
    }
};