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

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

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;
    }


目录
相关文章
|
9天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
9天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构的基本概念;算法的基本概念、特性以及时间复杂度、空间复杂度等举例说明;【含常见的报错问题及其对应的解决方法】
|
9天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
6月前
|
消息中间件 缓存 NoSQL
记一次蚂蚁金服四面遭虐,面试水太深,过河的渡船你造好了吗?
有道无术,术可成;有术无道,止于道;以术识道,以道御术
|
6月前
|
消息中间件 Dubbo Java
疫情下的机遇,阿里直招怒斩"P7"offer,自曝狂啃六遍的面试笔记
工作肯定会找的,面试肯定要过的,小编在这里为大家整理了我的一位朋友,一位从中游公司跳槽到阿里P7的面试题库
|
前端开发 Java 测试技术
秋招搞个保底offer再说,我换赛道了。
我是24届的应届生,大连某双非大四在读,Golang技术栈,秋招投了100多家公司了,面试有七八家,给机会的大厂也有,比如字节、京东就给机会了,但是都没抓住,都是一面就没后文了。。。 面试结束后,我反思了一下自己,感觉自己还是太差了,基础知识掌握的不够到位,很多问题都只能回答个七七八八,做不到深入叙述,我想主要原因是因为自己没有学,而是直接背的您的学习笔记,这就导致我根本无法对面试官的问题进行进一步延伸。
106 0
|
编译器 C语言 C++
重生之我要学C++第四天
重生之我要学C++第四天
91 0
惊险!备战3个月,五面蚂蚁金服差点倒在最后一面
作为程序员,免不了要经历面试这关,虽然平时工作勤勤恳恳,但是面试上面未必能展示的出来,比如平时都是做增删改查的业务系统,面试官非要问你如何处理高并发大数据,本来是写java代码,非要问你大型网站架构,这些问题防不胜防,本文就自己一次在蚂蚁金服的面试经验来总结一下,抛砖引玉。
|
存储 缓存 网络协议
裸辞-疫情-闭关-复习-大厂offer(二)(中)
裸辞-疫情-闭关-复习-大厂offer(二)
104 0
|
存储 缓存 编解码
裸辞-疫情-闭关-复习-大厂offer(一)(中)
裸辞-疫情-闭关-复习-大厂offer(一)
84 0