LeetCode Java两个单链表相交的一系列问题

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

题目描述

单链表可能有环,也可能无环。给定两个单链表的头节点 head1和head2,这两个链表可能相交,也可能不相交。

请实现一个函数,如果两个链表相交,请返回相交的第一个节点;如果不相交,返回null 即可。

要求:如果链表1的长度为N,链表2的长度为M,时间复杂度请达到 O(N+M),额外空间复杂度请达到O(1)。

问题思考

如何获取单链表对应的入环节点;

LeetCode Java两个单链表相交的一系列问题
处理思路:采用快慢指针方式,快指针每次走两步,慢指针每次走一步,如果遍历结束也不相遇,则此链表无环,当两者相遇时,移动快指针到链表头,然后快慢指针每次走一步,再次相遇,则此节点必是入环节点;

针对单链表是否有环相交,需要考虑以下几种情况;

1. 两个链表都没有环的情况,可能存在相交节点;链表结构类似如下:LeetCode Java两个单链表相交的一系列问题
处理思路:如果两个链表长度一致,则直接遍历链表,找到同一个节点返回即可,如果长度不一致,则需要先对齐链表长度,然后再遍历链表,找到同一个节点返回;

  1. 两个链表一个有环,一个无环的情况,这种情况必然不可能相交,若相交,则必然都有环;
    LeetCode Java两个单链表相交的一系列问题
    3.两个链表都有环,则可能出现以下两种情况:
    • 入环节点是同一节点;
      LeetCode Java两个单链表相交的一系列问题
      处理思路:若环前节点数不相同,则需要先对齐环前链表长度,然后和1中相同方式处理即可;

    • 入环节点是不同节点;
      LeetCode Java两个单链表相交的一系列问题
      处理思路:从head1环节点开始遍历环,当节点等于head2环节点时,返回即可;文章来源地址https://www.toymoban.com/news/detail-512096.html

代码实现

public class FindFirstIntersectNode {

    public static class Node {
        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }


    public static Node getIntersectNode(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        //分别获取head1、head2对应的入环节点
        Node loop1 = getLoopNode(head1);
        Node loop2 = getLoopNode(head2);
        //两个单链表一个有环一个无环的时候不可能相交
        if (loop1 == null && loop2 == null) {
            return noLoop(head1, head2);
        }
        if (loop1 != null && loop2 != null) {
            return bothLoop(head1, loop1, head2, loop2);
        }
        return null;
    }

    /**
     * 两个链表都是有环链表【需要考虑入环节点是不是同一节点问题】
     *
     * @param head1
     * @param loop1
     * @param head2
     * @param loop2
     * @return
     */
    private static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
        Node cur1 = null;
        Node cur2 = null;
        if (loop1 == loop2) {
            //入环节点为同一节点,和处理无环方式基本类似
            cur1 = head1;
            cur2 = head2;
            int n = 0;
            //对齐入环前节点差值
            while (cur1 != loop1) {
                n++;
                cur1 = cur1.next;
            }
            while (cur2 != loop2) {
                n--;
                cur2 = cur2.next;
            }
            cur1 = n > 0 ? head1 : head2;
            cur2 = cur1 == head1 ? head2 : head1;
            n = Math.abs(n);
            while (n != 0) {
                n--;
                cur1 = cur1.next;
            }
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        } else {
            //入环节点不是同一个节点,从入环节点loop1开始,转一圈看能不能遇到loop2.
            cur1 = loop1.next;
            while (cur1 != loop1) {
                if (cur1 == loop2) {
                    return loop1;
                }
                cur1 = cur1.next;
            }
            return null;
        }
    }

    /**
     */
    private static Node noLoop(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        Node cur1 = head1;
        Node cur2 = head2;
        int n = 0;
        while (cur1.next != null) {
            n++;
            cur1 = cur1.next;
        }
        while (cur2.next != null) {
            n--;
            cur2 = cur2.next;
        }
        //如果最终不是落在同一个节点上,则无交点
        if (cur1 != cur2) {
            return null;
        }
        //n为两个链表长度的差值
        //cur1取长度长的那个  cur2取另外一个
        cur1 = n > 0 ? head1 : head2;
        cur2 = cur1 == head1 ? head2 : head1;
        n = Math.abs(n);
        while (n != 0) {
            //将二者长度调整到一致
            n--;
            cur1 = cur1.next;
        }
        while (cur1 != cur2) {
            //同步遍历,相等时即为相交节点
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }


    /**
     * 获取对应链表的入环节
     *
     * @param head
     * @return
     */
    private static Node getLoopNode(Node head) {
        //2个节点无法形成环
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        //定义快慢指针
        Node slow = head.next;
        Node fast = head.next.next;
        while (slow != fast) {
            //移动结束 快慢指针也不相等,则一定无环
            if (fast.next == null || fast.next.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        //上面遍历结束,slow == fast 上述例子中会相遇,移动fast指针到头结点处
        fast = head;
        //再次移动快慢指针,则再次相遇节点必为入环节点
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;

    }


    public static void main(String[] args) {
        // 1->2->3->4->5->6->7->null
        Node head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);

        // 0->9->8->6->7->null
        Node head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(getIntersectNode(head1, head2).value);

        // 1->2->3->4->5->6->7->4...
        head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);
        head1.next.next.next.next.next.next = head1.next.next.next; // 7->4

        // 0->9->8->2...
        head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next; // 8->2
        System.out.println(getIntersectNode(head1, head2).value);

        // 0->9->8->6->4->5->6..
        head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(getIntersectNode(head1, head2).value);

    }
}

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

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

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

相关文章

  • 安装fasttext的一系列问题(全)

    环境配置:windows10+python3.10 前言:Gensim中的fasttext不能做文本分类,对于想学习fasttext进行文本分类、情感分析的同学还是必须下载Facebook的fasttext 在该python libs (或者粘贴该链接https://www.lfd.uci.edu/~gohlke/pythonlibs/#fasttext)搜索fasttext 下载whl文件,文件名: fasttext-0.9.2-cp310-cp31

    2024年02月06日
    浏览(60)
  • 力扣每日一道系列 --- LeetCode 88. 合并两个有序数组

    📷 江池俊: 个人主页 🔥个人专栏: ✅数据结构探索 ✅LeetCode每日一道 🌅 有航道的人,再渺小也不会迷途。 LeetCode 88. 合并两个有序数组 首先创建一个临时数组,其大小为第一个数组的大小(即nums1Size),其作用主要是。 通过循环遍历两个数组,将两个数组元素比较后较

    2024年02月04日
    浏览(51)
  • 关于秒杀系统的一系列问题

    阻塞队列怎么么实现?超卖问题?整体怎么实现? 5 设计一个秒杀系统 特点:高并发,请求量远大于库存量,只有少数能成功;逻辑比较简单,下单减库存; 设计理念:**限流,**只有少部分流量能进入后端; 削峰 ,将瞬间的高流量转换成平稳的流量(比如异步处理)。 内

    2024年02月01日
    浏览(33)
  • 如何判断两个多边形是否相交?——多边形相交判定算法详解

    如何判断两个多边形是否相交?——多边形相交判定算法详解 在计算机图形学中,判断两个多边形是否相交是一项很重要的任务。这涉及到各种应用场景,如碰撞检测、模拟物理效果等。在本篇文章中,我们将会介绍多边形相交判定算法的相关知识和实现方式。 首先,我们

    2024年02月14日
    浏览(67)
  • Mybatis引出的一系列问题-动态 SQL

    动态 SQL 是 MyBatis 的强大特性之一。如果你使用过 JDBC 或其它类似的框架,你应该能理解根据不同条件拼接 SQL 语句有多痛苦,例如拼接时要确保不能忘记添加必要的空格,还要注意去掉列表最后一个列名的逗号。利用动态 SQL,可以彻底摆脱这种痛苦。 使用动态 SQL 最常见情

    2024年02月14日
    浏览(38)
  • Java LeetCode篇-深入了解关于单链表的经典解法

       🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍   文章目录         1.0 移除链表元素         1.1 使用双指针方法         2.0 反转链表         2.1 递归法         2.2 头插法         3.0 链表中倒数第 k 个节点         3.1 递归法  

    2024年02月05日
    浏览(83)
  • Mybatis引出的一系列问题-JDBC 的探究

    一般来说,Java应用程序访问数据库的过程是: 装载数据库驱动程序; 通过jdbc建立数据库连接; 访问数据库,执行sql语句; 断开数据库连接。 程序开发过程中,存在很多问题: 首先,每一次web请求都要建立一次数据库连接。建立连接是一个费时的活动,每次都得花费0.05

    2024年02月14日
    浏览(40)
  • 判断两个矩形是否相交(Rect Intersection)

    最近在开发一个2D组态图形组件的过程中,里面的数学模块,涉及到两个矩形是否相交的判断。 这个问题很多年前就写过,算是个小的算法吧。 网络上搜索一下,有很多思路,有一些思路要基于多种组合的判断,显得比较复杂。 比如两个矩形相交的情形,可能有下面的多种

    2024年02月08日
    浏览(52)
  • python 安装库pycrypto失败的一系列问题[已解决]

    需要安装pycrypto这个库。 说来难受,后面发现这个貌似不再维护了,可以安装另外一个库pycryptodome,是这个库的延伸版本,和这个库的作用是一样的,我也是看别人的。 安装pycryptodome 安装pycrypto 需要 安装pycrypto 的继续:注意 3.9以上版本的python可能都无法使用 。存在一个错

    2024年04月09日
    浏览(79)
  • 利用python计算两个平面相交直线的方向向量

    利用两平面的法向量做”叉乘“运算获得两平面交线的方向向量。 如图所示,两平面相交关系为: 图中 n 1 ⃗ vec{n_1} n 1 ​ ​ 为平面1的法向量, n 2 ⃗ vec{n_2} n 2 ​ ​ 为平面2的法向量, l ⃗ vec{l} l 为两平面交线的方向向量。根据丘维声所著《解析几何(第三版)》第3

    2024年02月05日
    浏览(43)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包