C语言：相交链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了C语言：相交链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

C语言：相交链表,C语言,数据结构,C语言刷题,经验分享,数据结构,c语言

Lei宝啊：个人主页

愿美好与我们不期而遇

题目：

描述

给你两个单链表的头节点 headA和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null

接口

struct ListNode *getIntersectionNode

(struct ListNode *headA, struct ListNode *headB) { }

示例

思路

走差距步，比地址不比值

可以想象的到，如果长的和短的一起走，走到相等的值不就是相同节点吗？

但是也可能会出现这种情况：

那么这样的话，比值就不可行了，但是如果节点相交，他们的地址一定是相同的。

也由此，我们可以通过最后的一个节点判断他们是否相交，如果他们最后一个节点地址相同，则相交，我们去找相交节点，否则返回NULL。

文章来源地址https://www.toymoban.com/news/detail-626543.html

实现代码

    int lenA = 1;
    int lenB = 1;

    struct ListNode* curA = headA;
    while(curA->next)
    {
        lenA++;
        curA = curA->next;
    }

    struct ListNode* curB = headB;
    while(curB->next)
    {
        lenB++;
        curB = curB->next;
    }

    if(curA != curB)
        return NULL;

    struct ListNode* fast = headA;
    struct ListNode* slow = headB;
    if(lenA < lenB)
    {
        fast = headB;
        slow = headA;
    }

    int k = abs(lenA-lenB);
    while(k--)
    {
        fast = fast->next;
    }

    while(fast != slow)
    {
        if(fast == slow)
            return fast;

        fast = fast->next;
        slow = slow->next;
    }
    return fast;

到了这里，关于C语言：相交链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！