【数据结构与算法 经典例题】相交链表求交点

简介: 【数据结构与算法 经典例题】相交链表求交点

一、问题描述

160. 相交链表 - 力扣(LeetCode)

如下图所示

二、解题思路

方法一:双循环对比法

  • 时间复杂度O(n^2)       空间复杂度O(1)

  • 链表A中的节点依次与链表B中的每个节点比较
  • 若出现节点相同,则相交且为第一个交点
  • 若链表A走到空依然没有相同的节点,则不相交

注意:暴力解法效率较低,不建议采用

方法二: 双指针

  • 时间复杂度O(n)           空间复杂度O(1)

  • 首先遍历链表求出两个链表的长度,求得长度的差值
  • 定义两个快慢指针,哪个链表长,快指针就指向哪个链表
  • 两个指针分别从两个链表的第一个节点开始遍历,快指针先走出一个长度差值,之后两个指针每移动一步,比较指向的节点是否相同
  • 若出现节点相同,则相交且为第一个交点
  • 若两个指针走到空依然没有相同的节点,则不相交

三、C语言代码实现

方法一实现代码

 struct ListNode 
{
    int val;
    struct ListNode *next;
};
 
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    ListNode*pcurA=headA;
    ListNode*pcurB=headB;
    while(pcurA)
    {
        pcurB=headB;
        while(pcurB)
        {
            if(pcurA==pcurB)
                return pcurA;
            pcurB=pcurB->next;
        }
        pcurA=pcurA->next;
    }
    return NULL;
}

方法二实现代码

 struct ListNode 
{
    int val;
    struct ListNode *next;
};
 
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
   ListNode*pcurA=headA;
   ListNode*pcurB=headB;
   int countA=0;
   int countB=0;
   while(pcurA)//求出链表长度
   {
        pcurA=pcurA->next;
        countA++;
   }
   while(pcurB)
   {
        pcurB=pcurB->next;
        countB++;
   }
   int tmp=abs(countA-countB);//长度差值
   ListNode*slow,*fast;
   if(countA<countB)
    {
        slow=headA;
        fast=headB;
    }
    else
    {
        slow=headB;
        fast=headA;
    }
    while(tmp--)//长链表先走差值的步数
    {
        fast=fast->next;
    }
    while(fast&&slow)//同步比较
    {
        if(fast==slow)
            return fast;
        fast=fast->next;
        slow=slow->next;
    }
    return NULL;
}

 

目录
打赏
0
0
0
0
17
分享
相关文章
|
3月前
|
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法,并分析时间复杂度,理解链表特点。实验内容包括循环链表应用(约瑟夫回环问题)、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践,加深对链表数据结构的理解和应用能力。
80 4
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
78 29
|
15天前
|
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
72 25
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
39 5
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
99 5
|
3月前
|
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
72 0
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
126 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
77 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
58 0
数据结构与算法学习十四:常用排序算法总结和对比