博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
链表中环的入口结点
阅读量:4353 次
发布时间:2019-06-07

本文共 1052 字,大约阅读时间需要 3 分钟。

题目描述:给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

思路分析:1.首先判断链表中是否有环:可以使用两个指针来解决,定义两个指针,一个指针一次走1步,一个指针走2步,如果走的快的指针追上了走的慢的指针,那么链表就包含环;

2.找到环的入口:如果有环,那么快慢指针会相遇在一个结点,此时让快的指针指向头指针,快慢指针同时重新移动,当两个再次相遇时便是环的入口点。

代码实现

/* public class ListNode {    int val;    ListNode next = null;    ListNode(int val) {        this.val = val;    }}*/public class Solution {    public ListNode EntryNodeOfLoop(ListNode pHead)    {        if(pHead==null||pHead.next==null)        {            return null;        }        ListNode fast = pHead.next.next;        ListNode slow = pHead.next;        //判断是否有环        while(fast!=slow)        {            if(fast.next.next!=null&&slow.next!=null)            {                fast = fast.next.next;                slow = slow.next;            }else{                return null;            }                    }        //寻找环的入口结点        fast = pHead;        while(fast!=slow)        {            fast = fast.next;            slow = slow.next;        }        return slow;    }}

 

转载于:https://www.cnblogs.com/Dream-chasingGirl/p/10305815.html

你可能感兴趣的文章
Linux之profile、bash_profile、bashrc文件
查看>>
数据库路由中间件MyCat - 背景篇(2)
查看>>
Python 基础 (-)
查看>>
程序员过关斩将--来自于静态方法和实例方法的联想翩翩
查看>>
6-02使用SQL语句向表中插入数据
查看>>
text-transform的各种属性
查看>>
Spring(一)——总体介绍
查看>>
iOS项目管理:目录结构和开发流程
查看>>
shell 初学者 必读 ,强烈推荐新手读
查看>>
oFixed() 方法
查看>>
【讨论】C++程序员是否该掌握某种汇编语言?
查看>>
在iOS上实现变换
查看>>
LeetCode题解之 Implement strStr()
查看>>
Sharepoint List Attachments in a Webpart : The Solution
查看>>
基于组件的游戏对象系统
查看>>
【JS控制图片显示的大小(图片等比例缩放)】
查看>>
五种实用DOM方法总结
查看>>
spring mvc 安全
查看>>
Spring boot 集成Solr
查看>>
.Net互操作2
查看>>