[java刷算法]牛客—剑指offer链表有环的入口、反转链表、合并排序链表

简介: ✨今日三剑JZ23 链表中环的入口结点JZ24 反转链表JZ25 合并两个排序的链表

文章目录


JZ23 链表中环的入口结点


题目描述


思路详解

本题采用快慢指针的思路解题。

对于判断有没有环,利用环没有末尾NULL,后半部分一定是环,然后快慢双指针相遇就代表有环。

那我们现在假定已经是一个有环的链表了,那么这个链表中怎么找到环的入口呢?在慢指针进入链表环之前,快指针已经进入了环,且在里面循环,这才能在慢指针进入环之后,快指针追到了慢指针,不妨假设快指针在环中走了n圈,慢指针在环中走了m圈,它们才相遇,而进入环之前的距离为x,环入口到相遇点的距离为y,相遇点到环入口的距离为z。快指针一共走了x+n(y+z)+y步,慢指针一共走了x+m(y+z)+y,这个时候快指针走的倍数是慢指针的两倍,则x+n(y+z)+y=2(x+m(y+z)+y),这时候x+y=(n−2m)(y+z)。因为环的大小是y+z,说明从链表头经过环入口到达相遇地方经过的距离等于整数倍环的大小:那我们从头开始遍历到相遇位置,和从相遇位置开始在环中遍历,会使用相同的步数,而双方最后都会经过入口到相遇位置这y个节点,那说明这y个节点它们就是重叠遍历的,那它们从入口位置就相遇。


代码与结果

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    //判断有没有环,返回相遇的地方
    public ListNode hasCycle(ListNode head) {
        //先判断链表为空的情况
        if(head == null)
            return null;
        //快慢双指针
        ListNode fast = head;
        ListNode slow = head;
        //如果没环快指针会先到链表尾
        while(fast != null && fast.next != null){
            //快指针移动两步
            fast = fast.next.next;
            //慢指针移动一步
            slow = slow.next;
            //相遇则有环,返回相遇的位置
            if(fast == slow)
                return slow;
        }
        //到末尾说明没有环,返回null
        return null;
    }
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode slow = hasCycle(pHead);
        //没有环
        if(slow == null)
            return null;
        //快指针回到表头
        ListNode fast = pHead;
        //再次相遇即是环入口
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}



JZ24 反转链表


题目描述


思路详解

最简单的一种方式就是使用栈,因为栈是先进后出的。实现原理就是把链表节点一个个入栈,当全部入栈完之后再一个个出栈,出栈的时候在把出栈的结点串成一个新的链表。


代码与结果

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
    Stack<ListNode> stack= new Stack<>();
    //把链表节点全部摘掉放到栈中
    while (head != null) {
        stack.push(head);
        head = head.next;
    }
    if (stack.isEmpty())
        return null;
    ListNode node = stack.pop();
    ListNode dummy = node;
    //栈中的结点全部出栈,然后重新连成一个新的链表
    while (!stack.isEmpty()) {
        ListNode tempNode = stack.pop();
        node.next = tempNode;
        node = node.next;
    }
    //最后一个结点就是反转前的头结点,一定要让他的next
    //等于空,否则会构成环
    node.next = null;
    return dummy;
}
}


JZ25 合并两个排序的链表


题目描述


思路详解

从头结点开始考虑,比较两表头结点的值,值较小的list的头结点后面接merge好的链表(进入递归了);

若两链表有一个为空,返回非空链表,递归结束;

当前层不考虑下一层的细节,当前层较小的结点接上该结点的next与另一结点merge好的表头就ok了;

每层返回选定的较小结点就ok;


终止条件:两链表其中一个为空时,返回另一个链表;

当前递归内容:若list1.val <= list2.val 将较小的list1.next与merge后的表头连接,即list1.next = Merge(list1.next,list2); list2.val较大时同理;

每次的返回值:排序好的链表头;


代码与结果

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null){
            return list2;
        }
        else if(list2==null){
            return list1;
        }
        if(list2.val>list1.val){
            list1.next = Merge(list1.next,list2);
            return list1;
        }
        else{
            list2.next = Merge(list1,list2.next);
            return list2;
        }
    }
}

相关文章
|
2月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
92 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
2月前
|
算法 搜索推荐 Java
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
这篇文章介绍了如何使用Java后端技术,结合Graphics2D和Echarts等工具,生成包含个性化信息和图表的海报,并提供了详细的代码实现和GitHub项目链接。
147 0
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
|
2月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
56 0
|
2月前
|
算法 Java Linux
java制作海报一:java使用Graphics2D 在图片上写字,文字换行算法详解
这篇文章介绍了如何在Java中使用Graphics2D在图片上绘制文字,并实现自动换行的功能。
150 0
|
2月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
34 0
|
2月前
|
算法 Java 测试技术
数据结构 —— Java自定义代码实现顺序表,包含测试用例以及ArrayList的使用以及相关算法题
文章详细介绍了如何用Java自定义实现一个顺序表类,包括插入、删除、获取数据元素、求数据个数等功能,并对顺序表进行了测试,最后还提及了Java中自带的顺序表实现类ArrayList。
34 0
|
4月前
|
设计模式 缓存 算法
揭秘策略模式:如何用Java设计模式轻松切换算法?
【8月更文挑战第30天】设计模式是解决软件开发中特定问题的可重用方案。其中,策略模式是一种常用的行为型模式,允许在运行时选择算法行为。它通过定义一系列可互换的算法来封装具体的实现,使算法的变化与客户端分离。例如,在电商系统中,可以通过定义 `DiscountStrategy` 接口和多种折扣策略类(如 `FidelityDiscount`、`BulkDiscount` 和 `NoDiscount`),在运行时动态切换不同的折扣逻辑。这样,`ShoppingCart` 类无需关心具体折扣计算细节,只需设置不同的策略即可实现灵活的价格计算,符合开闭原则并提高代码的可维护性和扩展性。
70 2
|
4月前
|
存储 Java 开发者
揭秘!HashMap底层结构大起底:从数组到链表,再到红黑树,Java性能优化的秘密武器!
【8月更文挑战第24天】HashMap是Java集合框架中的核心组件,以其高效的键值对存储和快速访问能力广受开发者欢迎。在JDK 1.8及以后版本中,HashMap采用了数组+链表+红黑树的混合结构,实现了高性能的同时解决了哈希冲突问题。数组作为基石确保了快速定位;链表则用于处理哈希冲突;而当链表长度达到一定阈值时,通过转换为红黑树进一步提升性能。此外,HashMap还具备动态扩容机制,当负载因子超过预设值时自动扩大容量并重新哈希,确保整体性能。通过对HashMap底层结构的深入了解,我们可以更好地利用其优势解决实际开发中的问题。
123 0
|
4月前
|
搜索推荐 算法 Java
|
4月前
|
搜索推荐 算法 Java
经典排序算法之-----选择排序(Java实现)
这篇文章通过Java代码示例详细解释了选择排序算法的实现过程,包括算法的基本思想、核心代码、辅助函数以及测试结果,展示了如何通过选择排序对数组进行升序排列。
经典排序算法之-----选择排序(Java实现)