关关的刷题日记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;
    }
};

照顾好自己的身体，控制好自己的情绪，加油！

以上就是关关关于这道题的总结经验，希望大家能够理解，有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390，也可以加入专知——Leetcode刷题交流群（请先加微信小助手weixinhao: Rancho_Fang）。 同时请，关注我们的公众号，获取最新关于专知以及人工智能的资讯、技术、算法等内容。扫一扫下方关注我们的微信公众号。