C语言:相交链表

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

题目:

描述

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

接口

struct ListNode *getIntersectionNode

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

示例

40279cf05dd941a59145a04102c2b33f.png


思路

走差距步,比地址不比值

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

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

0561d761370e4c73b5654a0e5a7c697d.png

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

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

b0a06185a3da4adb9354b65239c8693d.png


实现代码

    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;


目录
相关文章
|
7天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
32 4
|
26天前
|
算法
❤️算法笔记❤️-(每日一刷-160、相交链表)
❤️算法笔记❤️-(每日一刷-160、相交链表)
16 1
|
28天前
|
存储 缓存 C语言
C语言:链表和数组有什么区别
C语言中,链表和数组是两种常用的数据结构。数组是一种线性结构,元素在内存中连续存储,通过下标访问,适合随机访问且大小固定的情况。链表由一系列不连续的节点组成,每个节点存储数据和指向下一个节点的指针,适用于频繁插入和删除操作的场景,链表的大小可以动态变化。
|
7天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
24 0
|
29天前
|
C语言
无头链表再封装方式实现 (C语言描述)
如何在C语言中实现无头链表的再封装,包括创建节点和链表、插入和删除操作、查找和打印链表以及销毁链表的函数。
26 0
|
29天前
|
C语言
C语言链式结构之有头单链表再封装写法
本文介绍了如何使用C语言对有头单链表进行封装,包括节点的创建、链表的初始化、数据的插入和删除,以及链表的打印等功能。
15 1
|
29天前
|
C语言
C语言结构体链式结构之有头单链表
文章提供了一个C语言实现的有头单链表的完整代码,包括创建链表、插入、删除和打印等基本操作。
20 1
|
29天前
|
测试技术 C语言
单链表之无头链表(C语言版)
本文详细介绍了使用C语言实现无头单链表的方法,包括节点和链表结构的定义、链表的创建与销毁、节点的插入与删除,以及链表的打印等功能。文章通过具体的代码示例,展示了如何在无头链表中进行头插法、尾插法、自定义位置插入和删除,以及如何清空和销毁链表。
24 0
单链表之无头链表(C语言版)
|
29天前
|
C语言
无头链表二级指针方式实现(C语言描述)
本文介绍了如何在C语言中使用二级指针实现无头链表,并提供了创建节点、插入、删除、查找、销毁链表等操作的函数实现,以及一个示例程序来演示这些操作。
20 0
|
1月前
【数据结构】环形、相交、回文、分割、合并、反转链表
【数据结构】环形、相交、回文、分割、合并、反转链表
25 0