第三期:那些年,我们一起经历过的链表中的浪漫

简介: 第三期:那些年,我们一起经历过的链表中的浪漫

PS:每道题解题方法不唯一,欢迎讨论!每道题后都有解析帮助你分析做题,答案在最下面,关注博主每天持续更新。


1. 两个链表的第一个公共节点

“我走过我的世界,再从你的世界走一遍”

“你走过你的世界,再从我的世界走一遍”

“最终我们将相遇,可能在途中,可能在结尾。”

题目描述

输入两个链表,返回它们的公共节点。如没有公共节点返回null。

示例1

输入:listA = [1,2,3,4,5], listB = [6,7,2,3,4,5]

输出:value为8的节点

示例2

输入:listA = [1,2,3,4,5,6,7], listB = [8,9,6,7]

输出:value为6的节点

解析

这道题可以运用哈希集合,直接把一个链表的所以节点放入,然后在遍历另一条链表节点,遍历到第一个集合包含的节点,便是公共节点,返回此节点。如没有,返回null。

但这样空间复杂空为O(M + N);那有没有空间复杂度为O(1)的方法呢?答案是有的,这就要请出我们浪漫的双指针了。

我们构建两个节点指针p1, p2,p1 = headA,p2 = headB,让它们分别遍历自己的链表,在途中如果 p1 == p2,则返回p1 ,或则当p1 == null时,让p1 = headB,p2 == null时,p2 = headA,继续遍历,这次一定会经历p1 == p2,返回p1即可。

一句话:

你变成我,走过我走过的路。

我变成你,走过你走过的路。

然后我们便相遇了。

两个节点不断的寻找对方的身影,双向奔赴的爱情,岂不浪漫。


2.链表中间节点

题目描述

给你单链表的头结点 head ,请你找出并返回链表的中间结点。

如果有两个中间结点,则返回第二个中间结点

示例1

输入:[1,2,3,4,5]

输出:value值为3的节点

示例2

输入:[1,2,3,4]

输出:value值为3的节点

解析

为了找到你想要的,我可以忍受孤独,我可以付出一切,我愿意先行。

这道题也可以运用双指针,定义两个指针,一个是慢指针slow,另一个是快指针fast。初始,慢指针slow和快指针fast都指向链表的头节点。然后,快指针fast每次向前移动两步,慢指针slow每次向前移动一步,当快指针fast不能继续向前移动时,慢指针slow所指的节点就是中间节点。


答案

1.两个链表中第一公共节点

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //如果这个世界没有你
        if (headA == null || headB == null) {
            //我活着又有什么意义
            return null;
        }
        //为了寻找你
        ListNode pA = headA, pB = headB;
        //我们彼此开始努力
        while (pA != pB) {
            //在这平行世界中携手共进
            //寻找彼此的踪迹
            //没人把这当作游戏
            //互相探寻对方世界的奥秘
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        //是的,爱情能够创造奇迹
        //我们永远不分离
        return pA;
    }


2.链表中间节点

    public ListNode middleNode(ListNode head) {
        //你说你喜欢那个东西
        ListNode slow = head;
        ListNode fast = head;
        //我愿意忍受孤独,先行
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //祝你安好
        return slow;
    }


目录
相关文章
|
17天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
6月前
|
消息中间件 缓存 NoSQL
记一次蚂蚁金服四面遭虐,面试水太深,过河的渡船你造好了吗?
有道无术,术可成;有术无道,止于道;以术识道,以道御术
惊险!备战3个月,五面蚂蚁金服差点倒在最后一面
作为程序员,免不了要经历面试这关,虽然平时工作勤勤恳恳,但是面试上面未必能展示的出来,比如平时都是做增删改查的业务系统,面试官非要问你如何处理高并发大数据,本来是写java代码,非要问你大型网站架构,这些问题防不胜防,本文就自己一次在蚂蚁金服的面试经验来总结一下,抛砖引玉。
|
传感器 机器学习/深度学习 存储
重温工业4.0:(二)时光已过,她的魅力你不曾拥有
在整个工业4.0的实现过程中,肯定没有单一的、标准化的方法。
重温工业4.0:(二)时光已过,她的魅力你不曾拥有
【圣诞专场】刷完这套链表套题,面试官考链表的时候我笑出了声(中)
【圣诞专场】刷完这套链表套题,面试官考链表的时候我笑出了声
102 0
【圣诞专场】刷完这套链表套题,面试官考链表的时候我笑出了声(中)
|
存储 算法 索引
【圣诞专场】刷完这套链表套题,面试官考链表的时候我笑出了声(下)
【圣诞专场】刷完这套链表套题,面试官考链表的时候我笑出了声
126 0
|
算法 编译器
【圣诞专场】刷完这套链表套题,面试官考链表的时候我笑出了声(上)
数据结构与算法的重要性相信大家都已经非常清楚。其中链表更是其中的重中之重,很多兄弟就感觉,诶无非单链表双链表实现增删改查,非常简单。确实,链表虽然简单,但许多兄弟也仅仅是在自己的编译器上完成过链表的这些基础功能。那如何检验自己的链表水平呢?——这里我为大家排好了一套链表专题,题目由简到难,囊括链表所有题型,帮你完美过渡。其中我也附带了自身的详细题解,照着这套题目刷下去,相信大家对于链表的操作更加是得心应手。建议收藏,有空时可根据题目顺序训练。
100 0
|
SQL 移动开发 NoSQL
年末学弟四面阿里面经!
最近学弟把面试经历给我整理了下,我特意发出来给有需要的同学!
310 0
|
算法 开发者
在家待着,不如刷刷这些招聘模拟题!在线编程周赛邀你挑战
阿里云开发者社区在线编程免费开放,做题还能赢好礼。
在家待着,不如刷刷这些招聘模拟题!在线编程周赛邀你挑战