数据结构与算法——链表OJ题详解（2）

一、前言

哦了兄弟们，咱们上次在详解链表OJ题的时候，有一部分OJ题呢up并没有整理完，这一个星期呢，up也是在不断的学习并且沉淀着，也是终于把剩下的题给整理完毕了，现在继续分享给大家。

二、OJ续享

2.1相交链表

力扣160 相交链表链接

首先咱们先来判断什么样的链表才是相交链表：
画图展示：

那么在判断完毕之后，我们又该如何实现呢?(解题思路请看图中文字)

代码展示：

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    ListNode* pa = headA;
    ListNode* pb = headB;
    int sizeA = 0;
    int sizeB = 0;
    while(pa)
    {
        sizeA++;//计算A链表的节点个数
        pa = pa->next;
    }
    while(pb)
    {
        sizeB++;//计算B链表的结点个数
        pb = pb->next;
    }
    int gap = abs(sizeA-sizeB);//计算差值
    ListNode* shorth = headA;
    ListNode* longth = headB;
    if(sizeA>sizeB)//确定到底谁是长链表，谁是短链表
    {
        longth = headA;
        shorth = headB;
    }
    while(gap--)
    {
        longth = longth->next;//让长链表先走gap步
    }
    while(longth)//遍历找寻两个链表是否有相同结点
    {
        if(longth==shorth)
        {
            return longth;
        }
        shorth = shorth->next;
        longth = longth->next;
    }
    return NULL;
}

2.2环形链表1

力扣141 环形链表1链接

咱们还是先来判断怎样才是一个环形链表：
画图展示（解题思路请看图中文字）：

代码展示：

 typedef struct ListNode ListNode;//快慢指针
bool hasCycle(struct ListNode *head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            return true;
        }
    }
    return false;
}

2.2环形链表2

力扣142 环形链表2链接

刚刚我们实现了如何判断环形链表，那我们现在再来升级一下难度，在判断完是环形链表之后，再返回这个环开始的第一个结点。那么又具体怎么实现呢
画图展示（解题思路请看图中文字）：

代码展示：

 typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {
    

    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            ListNode* pcur = head;
            while (pcur != slow)
            {
                pcur = pcur->next;
                slow = slow->next;
            }
            return pcur;
        }
    }
    return NULL;
}

三、总结

到这里，数据结构——链表的一些基础的经典OJ题up就给大家全部分析完毕了。可能有一些宝子会比较疑惑——关于环形链表，快慢指针不是用来找链表的中间结点的吗？为什么这里也同样适用呢？我只能说，这个问题问得太好了。但是up这次先不给大家证明，我先把这个问题留给大家，宝子们可以开动你们的灵活小脑袋想想，后续up会专门出一期关于数学证明环形指针的内容(如果你们已经证明出来了，可以给我留言看咱们的思路是否相同)，大家敬请期待哦。最后，希望大家可以一键三连，谢谢大家！

每一次挥汗如雨，都是通往成功路上的坚实步伐。