LeetCode 160.相交链表

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

LeetCode 160.相交链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言


LeetCode 160.相交链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言
题目链接👉 LeetCode 160.相交链表👈

💡题目分析

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

LeetCode 160.相交链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言
LeetCode 160.相交链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言
LeetCode 160.相交链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言
LeetCode 160.相交链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言
LeetCode 160.相交链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言
LeetCode 160.相交链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言

💡解题思路

🚩步骤一:找尾节点

	struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;
    int lenA = 1,lenB = 1;

    while(tailA)
    {
        tailA = tailA->next;
        lenA++;
    }
    while(tailB)
    {
        tailB = tailB->next;
        lenB++;
    }

🚩步骤二:判断尾节点是否相等

判断尾节点是否相等,如果尾节点相等就是相交

if (tailA != tailB)
{
    return NULL;
}

🚩步骤三:找交点

🍄思路1

A链表所有节点跟B链表都比较一遍,相等的那个就是交点

这种暴力求解法解决这道题是没问题的。但是这种解法时间复杂度为 O(N^2) / O(N*M),要求优化到 O(N),所以我们不采用这种暴力解法,建议使用下一种解法👇

🍄思路2

分别定义两个链表的长度 lenA 和 lenB,长的先走abs(lenA - lenB)步(差距步),然后再同时走,第一个相等的就是相交节点

	//长的先走差距步
    int gap = abs(lenA - lenB); //abs函数是对整数进行取绝对值
    struct ListNode* longList = headA;
    struct ListNode* shortList = headB;
    if(lenA < lenB)
    {
        longList = headB;
        shortList = headA;
    }

    while(gap--)
    {
        longList = longList->next;
    }

    while(longList != shortList)
    {
        longList = longList->next;
        shortList = shortList->next;
    }

👇图解👇
LeetCode 160.相交链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言

此方法整体时间复杂度为:O(M+N) / O(N),空间复杂度为:O(1)

🔔接口源码

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;
    int lenA = 1,lenB = 1;

    while(tailA)
    {
        tailA = tailA->next;
        lenA++;
    }
    while(tailB)
    {
        tailB = tailB->next;
        lenB++;
    }

    //判断最后一个节点是否相等(是否相交)
    if(tailA != tailB)
    {
        return NULL;
    }

    //长的先走差距步
    int gap = abs(lenA - lenB);
    struct ListNode* longList = headA;
    struct ListNode* shortList = headB;
    if(lenA < lenB)
    {
        longList = headB;
        shortList = headA;
    }

    while(gap--)
    {
        longList = longList->next;
    }

    //一一对应比较,判断重叠节点(因为前面已经经过是否相交的判断,所以执行至此,必定是相交的)
    while(longList != shortList)
    {
        longList = longList->next;
        shortList = shortList->next;
    }

    //二者相等,任意一一个都是相交起始点
    return longList;
}

LeetCode 160.相交链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言

🥰希望烙铁们能够理解欧!

总结🥰
以上就是本题讲解的全部内容啦🥳🥳🥳🥳
本文章所在【C/C++刷题系列】专栏,感兴趣的烙铁可以订阅本专栏哦🥳🥳🥳
前途很远,也很暗,但是不要怕,不怕的人面前才有路。💕💕💕
小的会继续学习,继续努力带来更好的作品😊😊😊
创作写文不易,还多请各位大佬uu们多多支持哦🥰🥰🥰

LeetCode 160.相交链表,C/C++刷题系列,leetcode,链表,算法,数据结构,c语言文章来源地址https://www.toymoban.com/news/detail-652292.html

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 单链表OJ题:LeetCode--160.相交链表

    朋友们、伙计们,我们又见面了,本期来给大家解读一下LeetCode中第160道单链表OJ题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! 数据结构与算法专栏 : 数据结构与算法 个  人  主  页  : stackY、 C 语 言 专 栏 : C语言:从入门到精通  Lee

    2024年02月08日
    浏览(47)
  • 力扣---LeetCode160. 相交链表(代码详解+流程图)

    “风格相同的人总会相遇 千万个人中万幸得以相逢.” 本章的内容是力扣每日随机一题的部分方法的解析 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 160. 相交链表 link 根据题目这是两个问题

    2024年02月02日
    浏览(38)
  • [LeetCode]-160. 相交链表-141. 环形链表-142.环形链表II-138.随机链表的复制

    目录 160.相交链表  题目 思路 代码  141.环形链表  题目 思路 代码 142.环形链表II 题目 思路 代码 160. 相交链表 - 力扣(LeetCode) https://leetcode.cn/problems/intersection-of-two-linked-lists/description/ 给你两个单链表的头节点  headA  和  headB  ,请你找出并返回两个单链表相交的起始节点

    2024年02月05日
    浏览(48)
  • Day4|LeetCode 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、160.链表相交、142.环形链表

    LeetCode 24. 两两交换链表中的节点 题目链接:24. 两两交换链表中的节点 - 力扣(LeetCode) 视频链接:帮你把链表细节学清楚! | LeetCode:24. 两两交换链表中的节点_哔哩哔哩_bilibili 思路 给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。你不能只是单纯的改变节

    2024年02月16日
    浏览(53)
  • Leetcode刷题之两两交换链表中的结点和相交链表

    只有把抱怨环境的心情,化为上进的力量,才是成功的保证。       ——罗曼·罗兰 目录 🍉一.相交链表 💐1.双指针 🍍2.计算长度加双指针 🍒二.两两交换链表中的结点  🍌1.迭代  给你两个单链表的头节点  headA  和  headB  ,请你找出并返回两个单链表相交的起始节点

    2024年02月04日
    浏览(33)
  • 【每日算法】【160. 相交链表】

    ☀️博客主页:CSDN博客主页 💨本文由 我是小狼君 原创,首发于 CSDN💢 🔥学习专栏推荐:面试汇总 ❗️游戏框架专栏推荐:游戏实用框架专栏 ⛅️点赞 👍 收藏 ⭐留言 📝,如有错误请指正 📆 未来很长,值得我们全力奔赴更美好的生活✨ 老规矩,先介绍一下 Unity 的科

    2024年02月08日
    浏览(58)
  • LeetCode 刷题 数据结构 链表 203 移除链表元素

    Given the  head  of a linked list and an integer  val , remove all the nodes of the linked list that has  Node.val == val , and return  the new head . Example 1: Example 2: Example 3: Constraints: The number of nodes in the list is in the range  [0, 104] . 1 = Node.val = 50 0 = val = 50 今天leetcode的中文官网比较卡,所以是登录官网进行

    2024年02月14日
    浏览(33)
  • leetcode算法刷题——链表

    题意:删除链表中等于给定值 val 的所有节点。 示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例 2: 输入:head = [], val = 1 输出:[] 示例 3: 输入:head = [7,7,7,7], val = 7 输出:[] 在链表类中实现这些功能: get(index):获取链表中第 index 个节点的值。如果索引无效,

    2024年02月21日
    浏览(45)
  • LeetCode刷题系列之----->(指针玩转链表篇)(三)

    🍉博客主页:阿博历练记 📖文章专栏:数据结构与算法 🔍代码仓库:阿博编程日记 🌹欢迎关注:欢迎友友们点赞收藏+关注哦 现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后

    2024年02月04日
    浏览(38)
  • 代码随想录刷题第4天|LeetCode24、LeetCode19、LeetCode160、LeetCode142

    1、LeetCode24 两两交换链表中的节点 题目链接:24、两两交换链表中的节点 要想清楚终止条件,cur每次指向要交换的两个节点的前一个节点,cur = cur-next-next; 若链表元素个数为偶数 , 则最后时刻 cur-next = NULL; 若链表元素个数为奇数,则最后时刻 cur-next-next = NULL; 最后要返回

    2024年02月05日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包